In recursive DFS traversal of binary tree, we have three basic elements to traverse: root node, left subtree, and right subtree. Each traversal process nodes in a different order using recursion, where recursive code is simple and easy to visualize i.e. one function parameter and 3–4 lines of code. So the critical question would be: How do we convert it into iterative code using stack? Let’s think.
Stack is a useful data structure to convert a recursive code into an iterative code. In recursive code, under the hood, compiler uses call stack to convert it into an iterative code. This call stack stores information like local variables, input parameters, the current state of the function call, etc.
Sometimes iterative implementation using stack becomes complex due to many input variables, additional operations, and the complex nature of recursive calls. In some situations, recursion is simple, and we can easily convert it into an iterative code.
To convert recursive code into an iterative one, we need to mimic what compiler does when we run recursive code! For this purpose, we need to use stack data structure in our code to simulate the execution of recursion.
Preorder and inorder traversals are tail-recursive i.e. there are no extra operations after the final recursive call. So implementation using stack is simple and easy to understand. On other side, postorder traversal is non-tail recursive because there is an extra operation after the last recursive calls i.e. we process the root node. So the implementation of postorder using a stack would be a little tricky. But if we follow the basic order of processing nodes, it can be easy to visualize.
To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls in DFS traversal. We visit each node three times:
Let's simulate the iterative implementation of each traversal using stack. We will be using the following binary tree node structure:
class TreeNode
{
int data
TreeNode left
TreeNode right
}
Let's revise the preorder traversal: We first process the root node, then traverse the left subtree, and finally, traverse the right subtree. Tracking the flow of recursion will give us better picture.
Here is an idea of iterative simulation using stack: When we visit any node first time, we process it, push node into the stack (to process the right subtree of that node later), and go to the left child. If there is no left child, we grab one node from the top of the stack and go to the right child of that node. Now we continue the same process for subtree rooted at the right child of popped node. Let's understand it via clear implementation steps.
Condition 1: If (currNode != NULL)
We process the currNode and push it into treeStack. Now we move to the left child i.e. currNode = currNode->left. This process continues in a loop till we reach the leftmost end of binary tree i.e. currNode == NULL. At this stage, all ancestors of that node will be available on treeStack.
if (currNode != NULL)
{
process(currNode->data)
treeStack.push(currNode)
currNode = currNode->left
}
Condition 2: If (currNode == NULL)
Now we reached the leftmost end of binary tree. So we move to the parent of that node by popping a node from the top of treeStack. At this stage, we need to traverse the right subtree of parent node, so we assign currNode with the right child of popped node and continue the above process. Think!
if (currNode == NULL)
{
prevNode = treeStack.pop()
currNode = prevNode->right
}
void iterativePreorder(TreeNode root)
{
if(root == NULL)
return
Stack<TreeNode> treeStack
TreeNode currNode = root
TreeNode prevNode = NULL
while (treeStack.empty() == false || currNode != NULL)
{
if (currNode != NULL)
{
process(currNode->data)
treeStack.push(currNode)
currNode = currNode->left
}
else
{
prevNode = treeStack.pop()
currNode = prevNode->right
}
}
}
We can further optimise the above solution by pushing only the right children to the stack. The idea is simple:
void iterativePreorder(TreeNode root)
{
if(root == NULL)
return
Stack<TreeNode> treeStack
TreeNode currNode = root
while (treeStack.empty() == false || currNode != NULL)
{
if (currNode != NULL)
{
process(currNode->data)
if (currNode->right != NULL)
treeStack.push(currNode->right)
currNode = currNode->left
}
else
currNode = treeStack.pop()
}
}
If we simplify the preorder traversal for each node, we process the node first and then process the left and right children. To track this order using stack, we push right child before left child to ensure that left subtree is processed first. In other words: If we pop a node from stack, the left child comes before the right child.
void iterativePreorder(TreeNode root)
{
if(root == NULL)
return
Stack<TreeNode> treeStack
TreeNode currNode
treeStack.push(root)
while (treeStack.empty() == false)
{
currNode = treeStack.pop()
process(currNode->data)
if (currNode->right != NULL)
treeStack.push(currNode->right)
if (currNode->left != NULL)
treeStack.push(currNode->left)
}
}
Each node is pushed into and popped out of the treeStack only once. So we are doing constant number of operations for each node. Time complexity = n* O(1) = O(n).
Space complexity: We are using one stack and the size of stack depends on the height of binary tree. Think! So space complexity = O(h).
In inorder traversal, we first process the left subtree, then root node, and finally the right subtree. How do we simulate this process using stack? Let’s understand the flow of recursion.
Here is an idea of iterative simulation using stack: Before processing the left subtree of any node, we need to save that node on stack (to process that node and right subtree of that node later). Then we go to the left child of that node. After processing all nodes in the left subtree, we pop node from the top of stack, process it, and go to the right child of that node to traverse the right subtree. Let's understand it via the clear implementation steps.
Condition 1: If (currNode != NULL)
We push currNode into stack for processing currNode and right subtree later. Now we move to the left child i.e. currNode = currNode->left and push it into the stack. This step will continue in a loop till we reach the leftmost end of binary tree i.e. currNode == Null.
if (currNode != NULL)
{
treeStack.push(currNode)
currNode = currNode->left
}
Condition 2: If (currNode == NULL)
Now we reached the leftmost end of binary tree, so we move to the parent of that node by popping a node from the top of treeStack. We assign it with currNode, and process it. At this stage, we need to traverse the right subtree of parent node, so we assign currNode with the right child of popped node and continue the above process in loop. Think!
if (currNode == NULL)
{
currNode = treeStack.pop()
process(currNode->data)
currNode = currNode->right
}
void iterativeInorder(TreeNode root)
{
if(root == NULL)
return
Stack<TreeNode> treeStack
TreeNode currNode = root
while (treeStack.empty() == false || currNode != NULL)
{
if (currNode != NULL)
{
treeStack.push(currNode)
currNode = currNode->left
}
else
{
currNode = treeStack.pop()
process(currNode->data)
currNode = currNode->right
}
}
}
Each node is pushed into and popped out of treeStack only once. So we are doing constant number of operations for each node. Time complexity = n* O(1) = O(n).
Space complexity: We are using one stack and the size of stack depends on the height of binary tree. Think! So space complexity = O(h).
In postorder traversal, we first process left subtree, then we process right subtree, and finally process the root node. In other words, we process all nodes in left and right subtree before processing any node. How do we simulate this process using stack? Let’s track the flow of recursion.
Here is an idea of iterative simulation using stack: Before processing the left subtree of any node, we need to save two things on the stack: 1) Right child of the current node to process right subtree after the traversal of left subtree 2) Current node, so that we can process it after the traversal of right subtree. To simulate this, we can use two separate stacks to store these two nodes. But how do we track the nodes in a postorder fashion? Let’s understand it clearly via the implementation.
Condition 1: If (currNode != NULL)
If the right child of the currNode is not NULL, then we push the right child into the rightChildStack. Now we push the currNode into the mainStack and go to the left child. We continue the same process until we reach the leftmost end of the tree i.e currNode == NULL.
if(currNode != NULL)
{
if(currNode->right != NULL)
rightChildStack.push(currNode->right)
mainStack.push(currNode)
currNode = currNode->left
}
Condition 2: If (currNode == NULL)
Now we access the parent node of the currNode which is at the top of the mainStack. We access the top node and assign it with currNode. But before processing the currNode, we need to first process nodes in the right subtree.
currNode = mainStack.top()
if(!rightChildStack.isEmpty() && currNode->right == rightChildStack.top())
currNode = rightChildStack.pop()
else
{
process(currNode->data)
mainStack.pop()
currNode = NULL
}
void iterativePostorder (TreeNode root)
{
if(root == null)
return
Stack<TreeNode> mainStack
Stack<TreeNode> rightChildStack
TreeNode currNode = root
while(!mainStack.empty() || currNode != NULL)
{
if(currNode != NULL)
{
if(currNode->right != NULL)
rightChildStack.push(currNode->right)
mainStack.push(currNode)
currNode = currNode->left
}
else
{
currNode = mainStack.top()
if(!rightChildStack.isEmpty() && currNode->right == rightChildStack.top())
currNode = rightChildStack.pop()
else
{
process(currNode->data)
mainStack.pop()
currNode = NULL
}
}
}
}
Each node is pushed into and popped out of the mainStack only once. Similarly, in the worst case, each node is pushed into the rightChildStack at most once. So we are doing a constant number of operations for each node. Time complexity = n* O(1) = O(n).
Space complexity: We are using two different stacks where the size of each stack depends on the height of the binary tree. Think! So the space complexity = O(h).
Can we optimize the above postorder traversal? Is there any way to implement the post-order traversal using a single stack? Here is an implementation code using the one stack and O(n) extra memory. Is it look similar to the two-stack implementation? Think!
void iterativePostorderUsingSet(TreeNode root)
{
if(root == null)
return
Stack<TreeNode> treeStack
HashSet<TreeNode> visitedNodeSet
TreeNode currNode = root
while(!treeStack.empty() || currNode != NULL)
{
if(currNode != NULL)
{
if(visitedNodeSet.contains(currNode))
{
process(currNode)
currNode = NULL
}
else
{
treeStack.push(currNode)
if(currNode->right != NULL)
treeStack.push(currNode->right)
visitedNodeSet.add(currNode)
currNode = currNode->left
}
}
else
currNode = treeStack.pop()
}
}
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.