Inorder Tree Traversal Without Recursion In C++

January 24, 2021

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.

More About Inorder Traversal:

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

Algorithm:

Return if root is empty.
Store temp as root.
Continue the while loop until temp is not null or stack is not empty.
Keep adding the left child of temp until NULL is encountered.
Print the temp node.
Since all the left children are visited, change temp to its right child.

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 == NULL) return;
    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

Prepinsta Prime