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,

Table of Contents

**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**

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 Traversal**s

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.

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 Traversal**s

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

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 Traversal**s

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

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,

Try to draw a **recursion diagram** for the above tree.

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.

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,

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,

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,

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,

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 **confirm**s 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.

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