Inorder Tree Traversal in Binary Tree In C++

Inorder Tree Traversal

Inorder traversal is a depth first algorithm. There are three types of traversals in tree: Preorder, Inorder, Postorder. In this article, inorder tree traversal is performed using recursion.

C++ Program To Find Inorder Traversal in trees
Example Of Inorder Traversal - C++ Program To find inorder traversal

Steps To Find Inorder Traversal:

  1.  Leftmost node is 5 so print 5
  2.  Move back, print 8 and look for right child.
  3.  As there is no right child, print 12 and move to the right subtree.
  4. 13 is printed and whole subtree is covered.
  5. Print 15 and move to the right subtree.
  6. 18 and 54 are printed and tree is covered.
Stack Orientation - C++ Program To find inorder traversal

What is Inorder generally used for?

We generally use Inorder traversal technique on Binary Tress , as it fetches the values from the underlying set in order. Using Post-order traversal is also an option, but during post order traversal while delete or freeing nodes it can even delete or free an entire binary tree, which is not a favorable condition.

Algorithm To Find Inorder Traversal:

  1. If root is NULL, return NULL.
  2. Visit the left subtree.
  3. Print the node.
  4. Visit the right subtree.

Code:

#include <bits/stdc++.h>
using namespace std;
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void inorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Visit Left subtree
    inorder_traversal(root -> left);
    // Print the data
    cout << root -> data << ” “;
    // Print the right subtree
    inorder_traversal(root -> right);
}
int main() {
    Tree *root = new Tree(15);
    root -> left = new Tree(12);
    root -> right = new Tree(54);
    root -> left -> left = new Tree(8);
    root -> left -> right = new Tree(13);
    root -> left -> left -> left = new Tree(5);
    root -> right -> left = new Tree(18);
    inorder_traversal(root);
    return 0;
}


 

Output:

5 8 12 13 15 18 54 

 

Time Complexity To Find Inorder Traversal in Binary Tree

Time Complexity

O(n)

Space Complexity

O(h)