Traversal of Binary Tree

Simply put:

• Go to the left subtree
• Visit the Current Node
• Go to the right subtree

Let us also write the pseudocode for the recursive inorder traversal of a binary tree:

Example:

Pseudocode for the Recursive Inorder Traversal:

Explanation:

In the above code, we have just traversed the complete tree by recursively calling the left subtree, and once we reach a point where there is no more left node (or it is the leaf node), we backtrack to the node's parent node and perform our operation (print that node or perform any search activity on the node, etc). Having done that, we recursively call the inorder function to the right subtree. This process continues till we have visited all the nodes of our binary tree.

Let us take an example to clearly understand how does the inorder traversal of a binary tree works.

Below given is the image of a binary tree, where its inorder traversal is performed.

In the image, the dotted lines indicate the order in which we will visit each node. The blue lines indicate that we are going back (backtracking) after visiting a particular node.

Steps:

• At first, we traverse through the leftmost nodes, till we reach a leaf node, and do not have any node after that (or Null), since, in inorder traversal, we traverse through left -> root -> right.
• Once we reach the leaf node, we print the current node's value(print 4 here) and backtrack(marked in blue) and then print the value of that node (after that print 2 here, followed by 1)
• We perform the same till we find the right child.
• In that case, we go deep to the right child and print its value. We recursively follow these steps till we have traversed all the nodes of the tree.

One more popular way of inorder traversal is through iteration. We can iteratively traverse all the nodes, however, it is complicated as compared to the normal recursive traversal. The pseudocode for the iterative traversal of the binary tree is given below.

Pseudocode for the Iterative Inorder Traversal:

Steps involved:-

1. Initialize an empty stack
2. Run a while loop till the stack becomes empty $OR$ the node provided to the function is $null$ .
3. Inside the while loop :-
   • Check if the node is not null :
     • In that case, push the node inside the stack
     • And go to the node's left.
   • If the node is null (or we have reached a child node):
     • Pop the stack's element (stack.top()), and mark it as visited, or print that node
     • Go to the current node's right
4. Continue step 3 till the stack becomes empty or the node becomes null.

Time Complexity Analysis:

In general, if we want to analyze the time complexity of a tree traversal then we have to think in the terms of the number of nodes visited.

Hence, if a tree has $n$ nodes, then each node is visited only once in inorder traversal and hence the complexity of the inorder traversal of the binary tree is $O(n)$ .

Space Complexity Analysis:

The space complexity of the recursive inorder traversal is $O(h)$ for a tree of height $h$. The height of the tree is the length of the deepest node from the root.

This might look weird that the space complexity is $O(h)$, and not equal to $O(n)$, where $n$ is the number of nodes in the tree. But, in general, space complexity of recursion is always the height/depth of recursion stack.

This is because, once we are returning (or backtracking) from our visited nodes, then their addresses are removed from the stack. And, that space is re-used when we are making a new call from a level that is closer to the root. So the maximum numbers of memory addresses on the stack at any given time are the tree height.

However, in the case of a skewed tree, the height of the tree may be equal to the number of nodes in the tree, hence leading to an overall space complexity of $O(n)$ .

Applications of Inorder Traversal:

• In-order traversal is very commonly used on binary search trees because it returns the value of the tree in a sorted manner. More specifically, in an ascending (non-decreasing) order.

2. Preorder Tree Traversal

Just like the previously discussed inorder traversal, preorder traversal of binary tree is also a variant of the DFS. It is performed in a similar way as the inorder traversal is performed, but here the order of visiting the nodes is different than that of the inorder traversal.

In the case of the preorder traversal of binary tree, we visit the current node first. After that, we visit the leftmost subtree. Once we reach the leaf node(or have covered all the nodes of the left subtree), we move towards the right sub-tree. In the right subtree, we recursively call our function to do the traversal in a similar manner.

It follows the NLR structure. It means first visit the current node, followed by recursively visiting the left subtree and then the right subtree. Below given is an image for the same.

FYI: The pre-order traversal is a topologically sorted one because a parent node is processed before any of its child nodes is done.

Example:

Let us see the pseudocode for the preorder traversal of binary tree.

Pseudocode for the Recursive Pre-order Traversal:

Explanation:

Let us take an example to clearly understand how the preorder traversal of the binary tree works.

Below given is the image of a binary tree, where its preorder traversal is performed.

In the image, the dotted lines indicate the order in which we will visit each node. The blue lines indicate that we are going back (backtracking) after visiting a particular node.

From the above image it must be very clear that only after processing a particular node, the left subtree is processed, followed by the right subtree. These operations are defined recursively for each of the nodes. And hence, this recursive implementation is referred to as a Depth-first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.

For example, in the above image, we start by visiting the root, followed by the next nodes in the left subtree. After that, we recursively visit our right subtree.

Just like the inorder traversal, another popular way of preorder traversal is through iteration. We can iteratively traverse all the nodes, however, it is complicated as compared to the normal recursive traversal. The pseudocode for the iterative traversal of the binary tree is given below.

Pseudocode for the Iterative Preorder Traversal:

Steps Involved:

1. We first make sure if the root node is not null, in that case, we simply return.
2. After that, we initialize our stack as empty. We also push the current node (root node) in our stack.
3. We run a while loop through the stack, where the termination condition is when the stack becomes empty.
4. Inside the while loop:
   i. Pop the top element of the stack, and store it in a variable ( here "node" ). Mark that node as visited (or print the value of that node)
   ii. Check if the right of the node exists. In that case, push the right sub-tree of the node into the stack.
   iii. Check if the left subtree of the node exists. If it exists, then push it into the stack.
5. Continue the steps i, ii, and iii till the stack becomes empty.

An important point to be noted here is that, although the order in which the preorder traversal of binary tree occurs is, $Current -> Left -> Right$ , we pushed the right element before the left element in the stack. The main reason for doing so is, since the stack data structure follows the LIFO property, i.e. last in first out, so we push our left subtree at last so that it gets processed before the right subtree.

Time complexity Analysis:

If a tree has $n$ nodes, then each node is visited only once in the preorder traversal of binary tree, hence the complexity of the preorder traversal of the binary tree is $O(n)$.

Space Complexity Analysis:

The space complexity of the recursive preorder traversal of binary tree is $O(h)$ for a tree of height $h$. The height of the tree is the length of the deepest node from the root. This is because space complexity of recursion is always the height / depth of recursion. We have already discussed the reason for so in our inorder tree traversal space complexity analysis. However, in the case of a skewed tree, the height of the tree may be equal to the number of nodes in the tree, hence leading to an overall space complexity of $O(n)$ .

Applications of Preorder Traversal:

• Pre-order traversal of binary tree can be used to make a prefix expression (Polish notation) from the expression trees.
• Preorder traversal of binary tree is also used to create a copy of the tree. For example, if we want to create a replica (copy) of a tree, we simply put the nodes of the tree in an array with a pre-order traversal. Then, for each value of the array, we perform the insert operation on a new tree. Finally, we get a copy of the original tree.
• The pre-order traversal of binary tree also outputs the topologically sorted order, because a parent node is processed before any of its child nodes is done.

3. Postorder Traversal

After having discussed a lot on inorder and preorder traversal of binary tree, you might have actually understood how they apply dfs for their traversal. Similar to them is the Postorder traversal of binary tree, where, we basically visit the left subtree and the right subtree before visiting the current node in recursion.

Postorder follows the L->R->N order of traversing the binary tree.

Let us now discuss the iterative and the recursive algorithms for the postorder traversal of a binary tree.

Example:

Pseudocode for the Recursive Post-order Traversal:

Explanation:

Following are the steps involved in the postorder traversal of binary tree:

1. The base case for our recursive function is checking the current node, whether it is null or not. If it is null, we simply return from our function.
2. If the current node is not null, we recursively travel to the left sub-tree using node.left (if it exists).
3. Then we recursively visit the right subtree using the node.right (if it exists).
4. Finally, we mark our current node as visited and perform our required operation (such as printing the node).

Let us take an example to clearly understand how does the postorder traversal of the binary tree works.

Below given is the image of a binary tree, where its postorder traversal is performed.

In the image, the dotted lines indicate the order in which we will visit each node. The blue lines indicate that we are going back (backtracking) after visiting a particular node.

In the above image, we can see that, before processing any node, the left subtree is processed first, followed by the right subtree, and the node is processed last. These operations can be defined recursively for each node.

Pseudocode for the Iterative Postorder Traversal:

The iterative version of the postorder traversal of binary tree is so not straightforward as the inorder and preorder traversal of binary tree (but a popular question among interviewers). Let us look into the steps involved in the postorder traversal of binary tree.

Steps Involved:

1. We initialize an empty stack
2. We also keep a variable lastNodeVisited and initialize it to null.
3. We run a while loop through our stack, with the condition that the stack should not be empty or the node should not be null.
4. Inside the while loop, we check if the node is not null,
   i. Then simply push it inside the stack.
   ii. Point node to node.left
5. In case the node is null:
   i. Peek through the stack's top and store it in a variable (peekNode here)
   ii. if the peekNode.right is not null and the lastNodeVisited is not equal to the peekNode.right then simply point the current node to the peekNode.right
   iii. If any of the above conditions don't meet:
   iv. Mark the peekNode as visited
   v. Pop from the stack's top and store it in the lastNodeVisited.
6. Repeat the points 4 and 5 till the stack becomes empty.

Time Complexity Analysis:

If a tree has $n$ nodes, then each node is visited only once in the postorder traversal of binary tree, hence the complexity of the postorder traversal of the binary tree is $O(n)$ .

Space Complexity Analysis:

The space complexity of the recursive postorder traversal of binary tree is $O(h)$ for a tree of height $h$. The height of the tree is the length of the deepest node from the root. This is because space complexity of recursion is always the height/depth of recursion. We have already discussed the reason for so in our inorder tree traversal space complexity analysis. However, in the case of a skewed tree, the height of the tree may be equal to the number of nodes in the tree, hence leading to an overall space complexity of $O(n)$.

Applications of Postorder Traversal:

• Post-order traversal of binary tree can generate a postfix representation (Reverse Polish notation) of a binary tree.
• Postorder traversal of binary tree is also used to delete the tree. Because it is easier in post-order traversal where each node is freed after freeing its children.