Preorder Traversal Without Recursion in C++

Preorder Traversal Without Recursion

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

C++ Program To implement preorder without recursion

More About Preorder Traversal

  1. Preorder traversal is a depth first algorithm.
  2. We first print the value of the node,them move to the left subtree and finally to the right subtree.
  3. If we need to explore more about the node itself before inspecting its leaves, we use preorder traversal.
  4. Preorder traversal is used to find the prefix expression of an expression tree.

Algorithm:

  1. If root is empty, return.
  2. Push root to stack.
  3. Continue until stack is not empty.
  4. Print the top element of stack.
  5. Add the right and the left child of the top element.
C++ Program to implement preorder 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 preorder(Tree *root) {
    // If empty return;
    if (root == NULLreturn;
    stack <Tree *> s;
    s.push(root);
    // Continue till stack is empty 
    while (!s.empty()) {
        Tree *temp = s.top();
        // Print data
        cout << temp -> data << ” “;
        // Remove Data
        s.pop();
        // Add right child
        if (temp -> right != NULLs.push(temp -> right);
        // Add Left child
        if (temp -> left != NULLs.push(temp -> left);
    }
}
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 << “Preorder Traversal” << endl;
    preorder(root); 
    return 0;
}

 

Output:

Preorder Traversal
10 20 40 50 30

Time Complexity Of Preorder Traversal without Recursion

Time Complexity

O(n)

Space Complexity

O(n)