Iterative Binary Tree Traversal Using Stack (Preorder, Inorder and Postorder)

Introduction

In recursive DFS traversal, we have three basic elements to traverse: root node, left subtree, and right subtree. Each traversal process nodes in a different order, where recursive code is simple and easy to visualize i.e. one function parameter and 3-4 lines of code. The critical question is: How can we convert recursive tree traversal into an iterative tree traversal? Let’s think.

In recursive code, compiler uses call stack in the background to convert it into iterative code. This call stack stores information like local variables, input parameters, the state of function calls, etc. So, for iterative implementation, we need to mimic what compiler does when we run recursive code! In other words: We need to use an explicit stack to simulate the execution of recursion.

Sometimes, iterative implementation using a stack becomes complex due to many input variables, complex additional operations, and complex nature of recursive calls. In situations like binary tree traversal, recursion is simple, and we can easily convert it into iterative code.

Let's understand the nature of recursive tree traversal

Preorder and inorder traversals are tail-recursive, i.e., there are no extra operations after the final recursive call. So the implementation of preorder and inorder using a stack is easy to understand. On the other side, postorder traversal is non-tail recursive because there is one 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 order of nodes in recursive postorder, we can easily implement it iteratively!

To simulate the recursive tree traversal into an iterative traversal, we need to understand the flow of recursive calls. If we observe, we visit each node three times:

1. First time when recursion visits the node coming from the top. In preorder, we process nodes at this stage.
2. Second time when recursion backtracks from the left child after visiting all nodes in the left subtree. In inorder, we process nodes at this stage.
3. Third time when recursion backtracks from the right child after visiting all nodes in the right subtree. In postorder, we process nodes at this stage.

Iterative preorder traversal using stack

Let's revise the preorder traversal: We first process the root node, then traverse the left subtree, and finally, traverse the right subtree. So tracking the correct flow of recursion will give us a better picture.

We first process the root. Then go to the left subtree and process the root node of the left subtree. Then we continue going left in the same way until we reach the leftmost node.

• If the leftmost node is a leaf node: Then traversal of the leftmost node is done, and recursion will backtrack to its parent. It had already processed the parent when it was coming from the top. So recursion will go to the right child of the parent, process all nodes in the right subtree, and backtrack to parent. This process will continue further in a similar way.
• If the leftmost node has a right child: Recursion will go to the right subtree, process all nodes using the same process, and backtrack to the leftmost node. At this stage, the traversal of the subtree rooted at the leftmost node is done, so recursion will backtrack to parent. Now, a similar process will continue for the parent node.

The idea of iterative preorder traversal: 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 remove the top node from 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.

Implementation steps

We use a stack treeStack and pointer currNode to track the current node. At the start, we initialize currNode with the root node. Now we run a loop until treeStack is not empty or currNode != NULL. Inside the loop:

• If currNode != NULL: We process the currNode, push it into treeStack and move to the left child. This process will continue in a loop until we reach the leftmost end of the binary tree. At this stage, all ancestors of that node will be available on treeStack.
• If currNode == NULL: We have reached the leftmost end, so we move to the parent by removing the top node from treeStack. At this stage, we need to traverse the right subtree of the removed node. So we assign currNode to the right child of the removed node and continue the above process.

Implementation pseudocode

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.top()
            treeStack.pop()
            currNode = prevNode->right
        }
    }
}

Optimized version

In the above code, we are storing any node in the stack to access the right subtree of that node later in preorder. So instead of storing that node, we can directly store the right child of that node. This will help us to optimize the above solution by reducing the stack space. How? Think and explore!

• If (currNode != NULL), we process currNode and push its right child to the treeStack before moving to its left child. Otherwise, we set currNode to the top node of the treeStack and remove the top node. 

Implementation pseudocode

void iterativePreorderOptimized(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.top()
            treeStack.pop()
        }
    }
}

Another iterative implementation of preorder traversal using stack

If we observe the processing of each node during preorder traversal, it looks like this: We first process the node, then the left child, and finally the right child. To maintain this order using a stack, we process the node first, then push the right child, followed by the left child. This way, when we pop nodes from the stack, the left child will appear before the right child.

Implementation steps

1. We create an empty stack treeStack and push the root node.
2. We also use a pointer currNode to track the current node.
3. Now we run a loop until treeStack is empty.
4. We assign top node of the stack to currNode and remove the top node.
5. Now we process currNode.
6. If currNode has a right child, we push the right child onto the stack.
7. If currNode has a left child, we push the left child onto the stack.
8. Now we move to the next iteration of the loop.

Implementation pseudocode

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()
        process (currNode->data)
        
        if(currNode->right != NULL) 
            treeStack.push(currNode->right)
        
        if(currNode->left != NULL) 
            treeStack.push(currNode->left)
    }
}

Analysis of iterative preorder traversal

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. Time complexity = 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, space complexity is O(h).

Iterative inorder traversal using stack

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.

We start from the root node, then move to the root of the left subtree, and so on, until we reach the leftmost node. In this way, recursion will first process the leftmost node.

• If the leftmost node is a leaf node: The traversal of the leftmost node is complete, and recursion will backtrack to parent. Now, it will process the parent, move to the right subtree of the parent, process all nodes in the right subtree, and then backtrack to the parent. This process will continue in a similar manner.
• If the leftmost node has only a right child: Recursion will move to the right child of the leftmost node. After processing all nodes in the right subtree using the same process, recursion will backtrack to the leftmost node. Once the traversal of the leftmost node is complete, recursion will backtrack to parent. A similar process will continue for the parent.

The idea for iterative in-order using a stack: Before processing the left subtree of any node, we need to save that node on the stack to process the node and right subtree of that node later. So we keep moving left and inserting nodes inside the stack. Once we reach the NULL node, 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.

Implementation steps

We create an empty stack treeStack and declare a pointer currNode to track the current node. Now, we run a loop until treeStack is empty and currNode is NULL. Inside the loop:

• If currNode != NULL: We push currNode onto the stack and move to the left child. This process continues in a loop until we reach the leftmost end of the binary tree, where currNode == NULL.
• If currNode == NULL: We have reached the leftmost end, so we move to the parent of that node by popping a node from the top of treeStack. We assign this node to currNode and process it. At this stage, we need to traverse the right subtree of the parent, so we assign currNode to the right child of the parent and continue the process in a loop.

Implementation pseudocode

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()
            process (currNode->data)
            currNode = currNode->right
        }
    }
}

Analysis of iterative inorder traversal

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 = 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.

Iterative postorder traversal using stack

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 the root node. How can we simulate this process using a stack? Let's follow the flow of recursion.

We start from the root, then move to the root of left subtree, and so on, until we reach the leftmost node.

• If the leftmost node is a leaf node: The recursion will process the leftmost node, completing its traversal. Then recursion will backtrack to its parent. From there, the recursion will move to the right child, process all nodes in the right subtree, backtrack to the parent, and finally process the parent. This process continues similarly for other nodes.
• If the leftmost node has only a right child: The recursion will move to the right child of that node. After processing all nodes in the right subtree, the recursion will backtrack to the leftmost node and process it. Once the traversal of the leftmost node is complete, the recursion will backtrack to parent. From there, the recursion will move to the right child of the parent, process all nodes in the right subtree, backtrack, and finally process the parent. This process continues similarly for other nodes.

The idea of iterative post-order traversal: 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.

Implementation steps: Using two stacks

We declare two separate stacks: rightStack to store the right child and mainStack to store the current node. We also initialize an extra pointer, currNode, to track the current node during the traversal. Now we run a loop until either the mainStack is empty or currNode is not equal to NULL. 

If currNode != NULL: If the right child of the currNode is not NULL, we push the right child into the rightStack. 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: We need to move to the parent of currNode, which is at the top of mainStack. So, we access this topNode from mainStack.

• If rightStack is not empty and the top node of rightStack is the same as the right child of topNode, it means we have not yet traversed the right subtree of topNode. In this case, we pop the node from rightStack and set currNode to the right child of topNode.
• Otherwise, the traversal of the right subtree of the topNode is complete. So, we process the topNode and remove it from the mainStack. In the next iteration, the traversal will move back to the parent. The idea is simple: currNode is still NULL! This process of moving to the parent will continue in subsequent iterations until currNode is not NULL.

Implementation pseudocode

void iterativePostorder(TreeNode root) 
{
    if(root == NULL)
        return

    stack<TreeNode> mainStack
    stack<TreeNode> rightStack
    TreeNode currNode = root

    while(!mainStack.empty() || currNode != NULL) 
    {
        if(currNode != NULL) 
        {
            if(currNode->right != NULL)
                rightStack.push(currNode->right)

            mainStack.push(currNode)
            currNode = currNode->left
        } 
        else 
        {
            TreeNode topNode = mainStack.top()
            if(!rightStack.empty() && topNode->right == rightStack.top()) 
            {
                currNode = topNode->right
                rightStack.pop()
            }    
            else 
            {
                process(topNode->data)
                mainStack.pop()
            }
        }
    }
}

Analysis of iterative postorder

Each node is pushed into and popped out of the mainStack only once. Similarly, in the worst case, each node is pushed into the rightStack at most once. So we are doing a constant number of operations for each node. Time complexity = n * O(1) = O(n). We are using two different stacks, where the size of each stack depends on the height of the binary tree. So space complexity = O(h).

Optimized version: Post order traversal using a single stack

Can we optimize the above postorder traversal idea using a single stack? If we observe closely, we're using the rightStack solely to confirm whether the traversal of the right subtree of the mainStack top node (topNode) is complete. So, how can we eliminate the need for the rightStack? Here's an idea. Suppose we keep track of the prevNode during the traversal.

• If the traversal of topNode right subtree is complete, then prevNode will be equal to the right child of topNode in post order. In this case, we simply process the topNode, assign prevNode to topNode, and remove topNode from the mainStack.
• Otherwise, we traverse the right subtree of the topNode. So we assign currNode to topNode->right.

In this way, we can perform an iterative postorder traversal using a single stack while keeping track of the previously visited node using the prevNode pointer.

void iterativePostorderOptimized(TreeNode root) 
{
    if(root == NULL)
        return

    stack<TreeNode> mainStack
    TreeNode currNode = NULL
    TreeNode prevNode = NULL   

    while(mainStack.empty() == false || currNode != NULL) 
    {
        if(currNode != NULL) 
        {
            mainStack.push(currNode)
            currNode = currNode->left
        }
        else 
        {
            TreeNode topNode = mainStack.top()
            if(topNode->right != NULL && topNode->right != prevNode)
                currNode = topNode->right
            else 
            {
                process(topNode->data)
                prevNode = topNode
                mainStack.pop()
            }
        }
    }
}

Critical ideas to think!

• How can we implement all iterative DFS traversals without using a stack? One idea is to use threaded binary tree traversal or Morris Traversal.
• What would be the worst, best, and average cases of space complexity?
• In the postorder traversal using two stacks, how many operations will be performed on the rightStack in the best and worst case?
• Here is an implementation code using one stack and hash set to track the status of visited nodes. Does it look similar to the two-stack implementation? Think!

void iterativePostorder(TreeNode root) 
{
    if(root == NULL)
        return

    stack<TreeNode> treeStack
    HashSet<TreeNode> visited
    TreeNode currNode = root

    while(!treeStack.empty() || currNode != NULL) 
    {
        if(currNode != NULL) 
        {
            if(visited.search(currNode) == true) 
            {
                process(currNode-data)
                currNode = NULL
            }
            else 
            {
                treeStack.push(currNode)
                if(currNode->right != NULL)
                    treeStack.push(currNode->right)
                
                visited.insert(currNode)
                currNode = currNode->left
            }
        }
        else 
        {
            currNode = treeStack.top()
            treeStack.pop()
        }
    }
}

Critical concepts to explore further!

• Level order traversal of a binary tree
• Comparison of BFS vs DFS traversal
• Properties and types of binary trees
• Various binary tree operations such as insertion, deletion, construction, height, merging, searching, and other transformation and query operations.
• Array-based implementation of binary trees
• Properties of binary search trees

Problems to solve using DFS traversals

• Left view of a binary tree
• Maximum width of a binary tree
• Minimum depth of a binary tree
• Level with the maximum number of nodes
• Convert a binary tree into a mirror tree
• Find the diameter of a binary tree
• Print nodes at k distance from a given node
• Boundary traversal of the binary Tree
• Lowest common ancestor of two nodes in a binary tree
• Construct a binary tree from preorder and in-order Traversal

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!