tree traversal

Tree Traversals (Both Recursive and Iterative)

In this post, I am going to discuss basic DFS Tree Traversals in both recursive and iterative way.

The recursive way is a cakewalk but the iterative way is a trickier one to think, so I will try to derive iterative version from the recursive version solution.

So, let’s start,

Tree Traversals

There are two types of Tree Traversals-
(i) Depth First Search (DFS)
(ii) Breadth First Search (BFS)

We are going to discuss DFS Traversals in this post.

DFS Tree Traversals (Recursive)

DFS as the name suggests Depth First Search, in this traversal technique preference is given to depth of the tree, so it will try to traverse till it reaches the deepest nodes of the tree.

This algorithm starts from the root , traverses all the nodes firstly in left sub tree until it reaches the leaf node before exploring the nodes in right sub tree as well.

This Algorithm takes a sub tree first go as deep as it can until you hit the leaf node before taking the other paths.

Types of DFS Tree Traversal


tree traversals


Unlike linear Data Structures we can traverse Tree in many ways. The basics DFS Tree Traversals are PreOrder, InOrder and PostOrder Traversals and we will discuss it one by one.

Binary Tree is the combination of root, left subtree and right subtree. Our traversal methods basically decides the order in which way we want to visit.

typedef struct TreeNode
{
     int data;
     struct Node *left;
     struct Node *right;
} TreeNode;

PreOrder Tree Traversals

In PreOrder Traversal, we will visit root node first, then its left subtree and then right subtree. So here preference of the order is given to root node.

tree traversals
PreOrder Traversal : A B D E C F G

In above Tree we visit root A first, then move to its left subtree. Again in that subtree we print B first as it is the root of that subtree. This way we traverse whole tree.

Preference of the Order will be given to root first then to left subtree and at last right subtree.

Recursive Code in C/C++

void PreOrder(TreeNode *root)
{
     if(root == NULL) return;
     printf("%d ", root->data);
     PreOrder(root->left);
     PreOrder(root->right);
}

InOrder Tree Traversals

In InOrder Traversal, we will visit left subtree first, then explore the root and at last right subtree.

tree traversals
InOrder Traversal : D B E A C G F

In above Tree we will go to left subtree until it is NULL (A-> B-> D-> NULL) then we will visit the root D first, since root D doesn’t have right child so we will return to previous recursion call, print node B then move to its right subtree to print E. This way we traverse whole tree.

Preference of the Order will be given to left subtree first then to root of the subtree and at last right subtree.

Recursive Code in C/C++

void InOrder(TreeNode *root)
{
     if(root == NULL) return;
     InOrder(root->left);
     printf("%d ", root->data);
     InOrder(root->right);
}

PostOrder Tree Traversals

In PostOrder Traversal, we will visit left subtree first, then right subtree and at last we will explore the root.

tree traversals
PostOrder Traversal : D E B G F C A

In above Tree we will go to left subtree until it is NULL (A-> B-> D-> NULL) then we will go to its right subtree since root D doesn’t have a right child so we will print root D, return to previous recursion call, then move to its right subtree to print E and at last print B. This way we traverse the whole tree.

Preference of the Order will be given to the left subtree first then to right subtree and at the root of the Tree.

Recursive Code in C/C++

void PostOrder(TreeNode *root)
{
     if(root == NULL) return;
     PostOrder(root->left);
     PostOrder(root->right);
     printf("%d ", root->data);
}

DFS Tree Traversals (Iterative)

Recursive Solutions are cakewalk and hope you understood it well, now I am going to discuss iterative solutions. Iterative Solutions are asked in interviews and it is not so easy to think it in that way.

Iterative PreOrder Traversal

For understanding iterative Solutions, you must be clear with the recursive solution. I will try to derive an iterative solution from a recursive solution.

Let’s take an example,

tree traversals

Try to draw a recursion diagram for the above tree.

tree traversals

This is how Recursion Tree looks like and if you observe it clearly, recursion uses a virtual stack to perform its operation.

Like for performing operations on ‘D’, ‘B’ was in that stack, similarly for performing activity on ‘B’, ‘A’ was in the stack.

Let’s see it diagrammatically how recursion uses the virtual stack.

tree traversals
tree traversals

This is how the virtual stack works in recursion. In the iterative solution, we just have to replace the virtual stack with the real stack to perform these operations.

I hope you are getting this idea clearly. This is the basic idea of the iterative solution.

Conversion of Recursive to Iterative Solution

Now forget about Recursion, just try to analyse the working of stack and that’s it, we just have to write code accordingly.

(i) First, we will push root in the stack and print its data.
(ii) Then move to its left node, if the left node is present, we will again push it into the stack.
(iii) Continue this process until the left node is NULL.

(iv) Else, pop from the stack and check whether the right node of the popped data exists or not.
(v) If it exists then again check for the left node as we did before.
(vi) If not we will continue to pop nodes from the stack.

Let’s see its code,

void PreOrder(TreeNode* root) {

   if(root == NULL) return;

    stack<TreeNode*> st;
    TreeNode *ptr = root;

    while(1)
    {   
        if(ptr)
        {
            st.push(ptr);
            printf("%d ",ptr->data);
            ptr = ptr->left;
        }
        else
        {
            if(st.empty()) break;
            TreeNode *temp = st.top();

            st.pop();
            if(temp->right) ptr = temp->right;
        }
    }
}

Yes, this is the code, it is just the reflection of the logic which we discussed earlier. So, I think code must be clear.

Iterative InOrder Traversal

Iterative InOrder Traversal is similar to iterative PreOrder Traversal.

In previous code, we were pushing root to the stack, then printing root’s data, and then we were moving to it’s left node.

Here, we have to push the root to the stack until root-> left is not NULL and then while popping nodes we will print that node’s data, and lastly, we will move to its a right node.

void inOrder(TreeNode* root) {

    if(root == NULL) return v;

    stack<TreeNode*> st;
    TreeNode *ptr = root;

    while(1)
    {   
        if(ptr)
        {
            st.push(ptr);
            ptr = ptr->left;
        }
        else
        {
            if(st.empty()) break;
            TreeNode *temp = st.top();

            printf("%d ", ptr->data);

            st.pop();
            if(temp->right) ptr = temp->right;
        }
    }
}

Iterative PostOrder Traversal

Iterative PostOrder will be different from the above two. The reason behind it is because in PostOrder Traversal we are simultaneously pausing two recursive calls.

Let’s understand it more clearly,

tree traversals

For this above tree, first left part will be processed then right part will be processed at last root will be explored.

Let’s see it’s recursion diagram,

tree traversals

For processing Node B, first node D will get pause and then node E will get pause simultaneously.

So at a time, two recursive calls will get pause, so this is the reason behind the complex iterative PostOrder Traversal.

But once if you can analyse it with the help of virtual stacks, things will be clear.

Let’s start,

tree traversals

Now, D->left = NULL, so now we have to check whether D->right is present or not. Here D->right is NULL.

So, we print D, and then we pop the topmost element from the stack. (D)

Now, topmost element in stack is B, so we have to explore it’s right part of it first. Here we will get stuck because we don’t have any information whether right child of that node is present or not.

How to Overcome this problem ?

So, to overcome it, what we will do, we will put right child of the root node first in the stack and then the root, so this will give help us to retrieve the identity of right child, where we got stucked above.

Let’s understand it by the diagram,

tree traversals

Now D doesn’t have left child as well as right child, so we will print D and we will pop it from the stack.

Set topmost element (B) of the stack as root, and pop it, now check if root->right (E) is the topmost element in stack, if yes then it confirms that root has right child as well.

Hope you get this idea clearly, this is the main logic of the iterative post Order Traversal.

Let’s see stack diagram for the entire Tree and then we will write the Algo and code accordingly.

tree traversals
tree traversals

This is the stack diagram of the PostOrder Iterative Traversal. Let discuss what we did,

(i) Push right child of the root and root to the stack and move to its left node, until root is NULL.
(ii) Pop the stack and if popped node equals topmost node of stack, then that node has right child as well.
(iii) If right child is present then pop the right child push that node and set current node as right child.
(iv) Continue it until stack is empty. That’s it

Let’s see the code for better clarification,

void postOrder(TreeNode* root) {

    stack<TreeNode*> st;
    TreeNode* ptr = root;
    
    while (!st.empty()) 
    {
        if (ptr) 
        {
            st.push(ptr);
            
            if(ptr->right) st.push(ptr->right)
            ptr = ptr->left;
        } 
        
        else 
        {
            ptr = st.top();
            st.pop();
            
            if (ptr->right == st.top()) 
            {
                st.pop();
                
                st.push(ptr);
                ptr = ptr->right;
            } 
            
            else {
                printf("%d ",root->data);
                ptr = NULL;
            }
        }
    }
}

I hope this explanation and code are clear to you.

I have discussed Tree DFS Traversals in both the Recursive and Iterative approaches. I hope it is clear.

That’s all folks..!!!

Learn Clone A linked List

Learn Rat in a maze problem

Learn Celebrity problem MasterStroke

Learn Duplicate and Missing Number

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

3 Comments

  1. Took me time for you to check out all the comments, but I truly enjoyed the content. It proved to be in fact helpful to me and I’m sure to all of the commenters right here! It’s usually huge when you can not just be informed, but additionally engaged! I’m certain you had enjoyable writing this write-up.

Leave a Comment

Your email address will not be published. Required fields are marked *