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:
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:
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