Tree traversal
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); |
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: