Inorder Traversal of Binary Tree
Inorder traversal is defined as a type of tree traversal technique which follows the Left-Root-Right pattern, such that:
- The left subtree is traversed first
- Then the root node for that subtree is traversed
- Finally, the right subtree is traversed
Inorder traversal
Algorithm for Inorder Traversal of Binary Tree
The algorithm for inorder traversal is shown as follows:
Inorder(root):
- Follow step 2 to 4 until root != NULL
- Inorder (root -> left)
- Write root -> data
- Inorder (root -> right)
- End loop
How does Inorder Traversal of Binary Tree work?
Consider the following tree:
Example of Binary Tree
If we perform an inorder traversal in this binary tree, then the traversal will be as follows:
Step 1: The traversal will go from 1 to its left subtree i.e., 2, then from 2 to its left subtree root, i.e., 4. Now 4 has no left subtree, so it will be visited. It also does not have any right subtree. So no more traversal from 4
Node 4 is visited
Step 2: As the left subtree of 2 is visited completely, now it read data of node 2 before moving to its right subtree.
Node 2 is visited
Step 3: Now the right subtree of 2 will be traversed i.e., move to node 5. For node 5 there is no left subtree, so it gets visited and after that, the traversal comes back because there is no right subtree of node 5.
Node 5 is visited
Step 4: As the left subtree of node 1 is, the root itself, i.e., node 1 will be visited.
Node 1 is visited
Step 5: Left subtree of node 1 and the node itself is visited. So now the right subtree of 1 will be traversed i.e., move to node 3. As node 3 has no left subtree so it gets visited.
Node 3 is visited
Step 6: The left subtree of node 3 and the node itself is visited. So traverse to the right subtree and visit node 6. Now the traversal ends as all the nodes are traversed.
The complete tree is traversed
So the order of traversal of nodes is 4 -> 2 -> 5 -> 1 -> 3 -> 6.
Program to implement Inorder Traversal of Binary Tree:
Below is the code implementation of the inorder traversal:
C++
// C++ program for inorder traversals #include <bits/stdc++.h> using namespace std; // Structure of a Binary Tree Node struct Node { int data; struct Node *left, *right; Node( int v) { data = v; left = right = NULL; } }; // Function to print inorder traversal void printInorder( struct Node* node) { if (node == NULL) return ; // First recur on left subtree printInorder(node->left); // Now deal with the node cout << node->data << " " ; // Then recur on right subtree printInorder(node->right); } // Driver code int main() { struct Node* 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); root->right->right = new Node(6); // Function call cout << "Inorder traversal of binary tree is: \n" ; printInorder(root); return 0; } |
Java
// Java program for inorder traversals import java.util.*; // Structure of a Binary Tree Node class Node { int data; Node left, right; Node( int v) { data = v; left = right = null ; } } // Main class class GFG { // Function to print inorder traversal public static void printInorder(Node node) { if (node == null ) return ; // First recur on left subtree printInorder(node.left); // Now deal with the node System.out.print(node.data + " " ); // Then recur on right subtree printInorder(node.right); } // Driver code public static void main(String[] args) { Node 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 ); root.right.right = new Node( 6 ); // Function call System.out.println( "Inorder traversal of binary tree is: " ); printInorder(root); } } // This code is contributed by prasad264 |
Python3
# Structure of a Binary Tree Node class Node: def __init__( self , v): self .data = v self .left = None self .right = None # Function to print inorder traversal def printInorder(node): if node is None : return # First recur on left subtree printInorder(node.left) # Now deal with the node print (node.data, end = ' ' ) # Then recur on right subtree printInorder(node.right) # Driver code if __name__ = = '__main__' : root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.right = Node( 6 ) # Function call print ( "Inorder traversal of binary tree is:" ) printInorder(root) |
C#
// C# program for inorder traversals using System; // Structure of a Binary Tree Node public class Node { public int data; public Node left, right; public Node( int v) { data = v; left = right = null ; } } // Class to store and print inorder traversal public class BinaryTree { // Function to print inorder traversal public static void printInorder(Node node) { if (node == null ) return ; // First recur on left subtree printInorder(node.left); // Now deal with the node Console.Write(node.data + " " ); // Then recur on right subtree printInorder(node.right); } // Driver code public static void Main() { Node 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); root.right.right = new Node(6); // Function call Console.WriteLine( "Inorder traversal of binary tree is: " ); printInorder(root); } } |
Javascript
// JavaScript program for inorder traversals // Structure of a Binary Tree Node class Node { constructor(v) { this .data = v; this .left = null ; this .right = null ; } } // Function to print inorder traversal function printInorder(node) { if (node === null ) { return ; } // First recur on left subtree printInorder(node.left); // Now deal with the node console.log(node.data); // Then recur on right subtree printInorder(node.right); } // Driver code const 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); root.right.right = new Node(6); // Function call console.log( "Inorder traversal of binary tree is: " ); printInorder(root); |
Inorder traversal of binary tree is: 4 2 5 1 3 6
Explanation:
How inorder traversal works
Complexity Analysis:
Time Complexity: O(N) where N is the total number of nodes. Because it traverses all the nodes at least once.
Auxiliary Space: O(1) if no recursion stack space is considered. Otherwise, O(h) where h is the height of the tree
- In the worst case, h can be the same as N (when the tree is a skewed tree)
- In the best case, h can be the same as logN (when the tree is a complete tree)
Use cases of Inorder Traversal:
In the case of BST (Binary Search Tree), if any time there is a need to get the nodes in non-decreasing order, the best way is to implement an inorder traversal.
Related Articles:
Contact Us