Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Inorder Tree Traversal Without Recursion In C++

Inorder Tree Traversal Without Recursion

There are three types of traversals in trees: Preorder, Inorder and Postorder. The traversals can be performed using recursion or stack. In this article, inorder traversal is performed using stacks.

 

C++ program for Inorder Traversal without recursion

More About Inorder Traversal:

  1. Inorder Traversal is a depth first algorithm.
  2. In Inorder Traversal, we first move to the left subtree, then print the node and finally move to the right subtree.
  3. If you want the orginal sequence or how the tree was made, we use the inorder sequence.
  4.  Inorder Traversal of a binary search tree gives the sequence in non decreasing order.

Algorithm:

  1. Return if root is empty.
  2. Store temp as root.
  3. Continue the while loop until temp is not null or stack is not empty.
  4. Keep adding the left child of temp until NULL is encountered.
  5. Print the temp node.
  6. Since all the left children are visited, change temp to its right child.
C++ Program to implement inorder traversal

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(Tree *root) {
    // If empty return;
    if (root == NULLreturn;
    stack  s;
    Tree * temp = root;
    // Continue till stack is empty or temp is not null
    while (!s.empty() || temp != NULL) {
        // Traverse the left subtree until NULL
        while (temp != NULL) {
            s.push(temp);
            temp = temp -> left;
        }
        temp = s.top();
        cout << temp -> data << ” “;
        // As visited pop
        s.pop();
        // Traverse the right subtree
        temp = temp -> right;
    }
}
int main() {
    Tree *root = new Tree(10);
    root -> left = new Tree(20);
    root -> right = new Tree(30);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(50);
    cout << “Inorder Traversal” << endl;
    inorder(root); 
    return 0;
}

Output:

Inorder Traversal
40 20 50 10 30

Time Complexity Of Inorder Traversal without Recursion

Time Complexity

O(n)

Space Complexity

O(n)