In recursive DFS traversal of a binary tree, we have three basic elements to traverse: the root node, the left subtree, and the right subtree. Each traversal process nodes in a different order using recursion, where the recursive code is simple and easy to visualize i.e. one function parameter and 3-4 lines of code. So the critical question is: How do we convert this recursive code into iterative code using a stack? Let’s think.
A stack is a useful data structure to convert recursive code into iterative code. In recursive code, the compiler uses the call stack to convert it into iterative code. This call stack stores information such as local variables, input parameters, the current state of function calls, etc.
Sometimes, iterative implementation using a 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 the compiler does when we run recursive code! For this purpose, we need to use the stack data structure in our code to simulate the execution of recursion.
The preorder and inorder traversals are tail-recursive, i.e., there are no extra operations after the final recursive call. So the implementation using a stack is simple and easy to understand.
On the other hand, the postorder traversal is non-tail recursive because there is an extra operation after the last recursive call - we process the root node. So implementing postorder using a stack can be a little tricky. But if we follow the basic order of processing nodes, it can be easy to visualize.
To simulate the recursive binary tree traversal into an iterative traversal, we need to understand the flow of recursive calls in DFS tree traversal. Here we visit each node three times:
Using the above insight, let's simulate the iterative implementation of each tree traversal using stack. We will be using following node structure of binary tree.
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 a better picture.
Here is an idea of iterative simulation using a stack: When we visit any node for the first time, we process it, push that 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 the subtree rooted at the right child of the 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 until we reach the leftmost end of the 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 that we have reached the leftmost end of the binary tree, 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 the parent node. So we assign currNode to the right child of the popped node and continue the above process.
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)
{
cout << currNode->data << " ";
treeStack.push(currNode);
currNode = currNode->left;
}
else
{
prevNode = treeStack.top();
treeStack.pop();
currNode = prevNode->right;
}
}
}
We can further optimize the above solution by adding only the right child 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)
{
cout << currNode->data << " ";
if (currNode->right != NULL)
treeStack.push(currNode->right);
currNode = currNode->left;
}
else
{
currNode = treeStack.top();
treeStack.pop();
}
}
}
If we simplify the preorder traversal for each node: We process the node first and then process the left and right child. To track this order using a stack, we can push the right child before the left child to ensure that the left subtree is processed first. In other words, if we pop a node from the 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.top();
treeStack.pop();
cout << 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 stack only once, so we are doing a constant number of operations for each node. The time complexity is n* O(1) = O(n). We are using one stack, and the size of the stack depends on the height of the binary tree. So, the space complexity is O(h).
In an inorder traversal, we first process the left subtree, then the root node, and finally the right subtree. How can we simulate this process using a stack? Let’s understand this by exploring the flow of recursion.
Here is an idea for iterative simulation using a stack: Before processing the left subtree of any node, we need to save that node on the stack (to process that node and the 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 the node from the top of the stack, process it, and go to the right child of that node to traverse the right subtree. Let's understand it via clear implementation steps.
Condition 1: If (currNode != NULL)
We push currNode onto the stack to process currNode and the right subtree later. Next, we move to the left child by assigning currNode = currNode->left and push it onto the stack. This step continues in a loop until we reach the leftmost end of the binary tree, i.e. currNode == NULL.
if (currNode != NULL)
{
treeStack.push(currNode)
currNode = currNode->left
}
Condition 2: If (currNode == NULL)
Now we have reached the leftmost end of the binary tree, so we move to the parent of that node by popping a node from the top of treeStack. We assign it to currNode and process it. At this stage, we need to traverse the right subtree of the parent node, so we assign currNode with the right child of the popped node and continue the above process in a 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.top();
treeStack.pop();
cout << currNode->val << " ";
currNode = currNode->right;
}
}
}
Each node is pushed into and popped out of the treeStack only once, so we are doing a constant number of operations for each node. The time complexity is n * O(1) = O(n).
The space complexity is O(h) since we are using one stack, and the size of the stack depends on the height of the binary tree.
In a postorder traversal, we first process the left subtree, then the right subtree, and finally the root node. In other words, we process all the nodes in the left and right subtrees before processing any node. How do we simulate this process using a 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) the right child of the current node to process the right subtree after the traversal of the left subtree, and (2) the current node, so that we can process it after the traversal of the 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 currNode, which is at the top of the mainStack. We assign the top node to currNode, but before processing it, we need to first process the 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.empty() && currNode->right == rightChildStack.top())
{
rightChildStack.pop();
mainStack.pop();
mainStack.push(currNode);
currNode = currNode->right;
}
else
{
cout << currNode->val << endl;
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. The time complexity is 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).
void iterativePostorderUsingSet(TreeNode* root)
{
if (root == NULL)
return;
stack<TreeNode*> treeStack;
unordered_set<TreeNode*> visitedNodeSet;
TreeNode* currNode = root;
while (!treeStack.empty() || currNode != NULL)
{
if (currNode != NULL)
{
if (visitedNodeSet.count(currNode) > 0)
{
// currNode has already been visited
cout << currNode->val << " ";
currNode = NULL;
}
else
{
// first visit to currNode
treeStack.push(currNode);
if (currNode->right != NULL)
treeStack.push(currNode->right);
visitedNodeSet.insert(currNode);
currNode = currNode->left;
}
}
else
{
// currNode is NULL, pop next node from stack
currNode = treeStack.top();
treeStack.pop();
}
}
}
void postorderTraversalSingleStack(TreeNode* root)
{
if (root == NULL)
return;
stack<TreeNode*> treeStack;
TreeNode* prevNode = NULL;
while (root != NULL || !treeStack.empty())
{
if (root != NULL)
{
treeStack.push(root);
root = root->left;
}
else
{
TreeNode* currNode = treeStack.top();
if (currNode->right != NULL && currNode->right != prevNode)
{
// go to right child if it exists and has not been visited
root = currNode->right;
}
else
{
// visit the current node
cout << currNode->val << " ";
prevNode = currNode;
treeStack.pop();
}
}
}
}
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!