Tree traversal

Sorting algorithm

The traversal of trees is very interesting, we can traverse trees in different ways. Recursion is also a very common way to traverse and manipulate tree structures.

Example: In this example, we will show all three traversal(inorder, postorder and preorder) using recursion.

Javascript

// javascript program for different tree traversals 
  
// Class containing left and right child of current 
// node and key value 
class Node { 
    constructor(val) { 
        this.key = val; 
        this.left = null; 
        this.right = null; 
    } 
} 
  
// Root of Binary Tree 
let root = null; 
  
// In-Order Traversal: Left -> Root -> Right 
function printInorder(node) { 
    if (node == null) 
        return; 
  
    // First recur on left child */ 
    printInorder(node.left); 
  
    // Then print the data of node 
    console.log(node.key); 
  
    // Now recur on right child 
    printInorder(node.right); 
} 
  
// Pre-Order Traversal: Root -> Left -> Right 
function printPreorder(node) { 
    if (node == null) 
        return; 
    // First print the data of node 
    console.log(node.key); 
  
    // then recur on left child */ 
    printPreorder(node.left); 
  
    // Now recur on right child 
    printPreorder(node.right); 
} 
  
// Post-Order Traversal: Left -> Right -> Root 
function printPostorder(node) { 
    if (node == null) 
        return; 
  
    // then recur on left child */ 
    printPostorder(node.left); 
  
    // Now recur on right child 
    printPostorder(node.right); 
  
    // First print the data of node 
    console.log(node.key); 
} 
  
  
// Driver method 
  
root = new Node(1); 
root.left = new Node(2); 
root.right = new Node(3); 
root.left.left = new Node(4); 
root.left.right = new Node(5); 
  
console.log("Inorder traversal of binary tree is "); 
printInorder(root); 
console.log("Preorder traversal of binary tree is "); 
printPreorder(root); 
console.log("Postorder traversal of binary tree is "); 
printPostorder(root);

Output

Inorder traversal of binary tree is 
4
2
5
1
3
Preorder traversal of binary tree is 
1
2
4
5
3
Postorder traversal of binary tree is 
4
5
2
3
1

Applications of Recursion in JavaScript

Recursion is a programming technique in which a function calls itself directly or indirectly. Using a recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. Recursion is a technique in which we reduce the length of code and make it easy to read and write. A recursive function solves a problem by calling its own function and also calling for the smaller subproblem.

Recursion is a powerful technique that has many applications in the field of programming. Below are a few common applications of recursion that we frequently use:

Tree and graph traversal
Sorting algorithms
Divide-and-conquer algorithms
Sieve of Eratosthenes
Fibonacci Numbers

Let’s deep dive into each application:

Tags:

#JavaScript-DSA #JavaScript-Program #JavaScript #Web Technologies

Sorting algorithm

Tree traversal

Javascript

Applications of Recursion in JavaScript

Similar Reads

Contact Us