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

Introduction to Iterative Binary Tree Traversal

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 the code of recursive tree traversal into an iterative tree traversal? Let’s think.

In recursive code, the compiler uses the 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 the compiler does when we run recursive code! In other words: We need to use an explicit stack to simulate the execution of recursion.

Sometimes, the iterative implementation using a stack becomes complex due to many input variables, additional operations, and the complex nature of recursive calls. In some 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 traversals using a stack is simple and 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 postorder, it can be easy to visualize.

One idea is clear: To simulate the recursive tree traversal into an iterative traversal, we need to understand the flow of recursive calls. In recursive tree traversal, we visit each node three times:

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

Using the above insight, let's simulate the iterative implementation of each tree traversal using stack. We will be using the following node structure of the binary tree.

//Node structure in C++
class TreeNode 
{
public:
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) 
    {
        data = value;
        left = NULL;
        right = NULL;
    }
};

//Node structure in Java
class TreeNode 
{
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) 
    {
        data = value;
        left = null;
        right = null;
    }
}

//Node structure in Python
class TreeNode:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

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 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 its parent node. Now, a similar process will continue for the parent node.
• If the leftmost node is a leaf node: Then the traversal of the leftmost node is done, and recursion will backtrack to its parent node. It had already processed the parent node when it was coming from the top. So recursion will go to the right child of the parent node, process all nodes in the right subtree, and backtrack to the parent node. This process will continue further in a similar way.

The overall idea of iterative preorder traversal 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 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 of the popped node.

Implementation steps of iterative preorder traversal

• We use a stack treeStack and temporary 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.

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 will continue 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 the currNode data.
• Push currNode into the treeStack.
• Go to the left child of currNode.

Condition 2: If (currNode == NULL)

Now we have reached the leftmost end of the binary tree, 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 top node. So we assign currNode to the right child of the removed top node and continue the above process.

If currNode == NULL:

• Access the parent node by removing the top node from treeStack.
• Go to the right child of the parent node.

C++ implementation of iterative preorder traversal

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;
        }
    }
}

Python implementation of iterative preorder traversal

def iterativePreorder(root):
    if root is None:
        return
    
    treeStack = []
    currNode = root
  
    while treeStack or currNode:
        if currNode:
            print(currNode.data, end=" ")
            treeStack.append(currNode)
            currNode = currNode.left
        else:
            prevNode = treeStack.pop()
            currNode = prevNode.right

Java method to implement iterative preorder traversal

public void iterativePreorder(TreeNode root) 
{
    if (root == null)
        return;

    Stack<TreeNode> treeStack = new Stack<>();
    TreeNode currNode = root;

    while (!treeStack.empty() || currNode != null) 
    {
        if (currNode != null) 
        {
            System.out.print(currNode.data + " ");
            treeStack.push(currNode);
            currNode = currNode.left;
        } 
        else 
        {
            TreeNode prevNode = treeStack.pop();
            currNode = prevNode.right;
        }
    }
}

Optimized version of the above approach

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.

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

C++ implementation code

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();
        }
    }
}

Python implementation code

def iterativePreorder(root):
    if root is None:
        return

    treeStack = []
    currNode = root

    while treeStack or currNode:
        if currNode:
            print(currNode.data, end=" ")

            if currNode.right is not None:
                treeStack.append(currNode.right)

            currNode = currNode.left
        else:
            currNode = treeStack.pop()

Java implementation code

public void iterativePreorder(TreeNode root) 
{
    if (root == null)
        return;

    Stack<TreeNode> treeStack = new Stack<>();
    TreeNode currNode = root;
    while (!treeStack.empty() || currNode != null) 
    {
        if (currNode != null) 
        {
            System.out.print(currNode.data + " ");
            if (currNode.right != null)
                treeStack.push(currNode.right);

            currNode = currNode.left;
        } 
        else
            currNode = treeStack.pop();
    }
}

Another Iterative Implementation of Preorder Traversal using Stack

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.

Implementation Steps

1. We create an empty stack, treeStack, and push the root node onto it.
2. We also use a pointer, currNode, to track the current node.
3. Now we run a loop until treeStack is empty.
4. We pop the top node of the stack and assign it to currNode. Now we process currNode.
5. If currNode has a right child (i.e., currNode->right != NULL), we push the right child onto the stack.
6. If currNode has a left child (i.e., currNode->left != NULL), we push the left child onto the stack.
7. Now we move to the next iteration of the loop.

C++ Implementation Code

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);
    }
}

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

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 first start from the root node and go to the left subtree, then to the root of the left subtree, and so on, until we reach the leftmost end of the tree. In this way, recursion will first process the leftmost node.
• If the leftmost node is a node with a right child only: Recursion goes to the right child of the leftmost node. After processing all nodes in the right subtree using the same process, recursion backtracks to the leftmost node. Now the traversal of the leftmost node is done, and recursion backtracks to its parent node. A similar process continues for the parent node.
• If the leftmost node is a leaf node: Then the traversal of the leftmost node is done, and recursion backtracks to its parent node. Now it processes the parent node, goes to the right subtree of the parent node, processes all nodes in the right subtree, and backtracks to the parent node. This process continues further in a similar way.

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.

Implementation Steps for Iterative Inorder Traversal

• We create an empty stack called treeStack and push the root node onto it.
• We also declare a pointer called currNode to track the current node.
• Now, we run a loop until either the treeStack is empty or the currNode is NULL.

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
}

C++ Implementation Code Iterative Inorder Traversal

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;
        }
    }
}

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

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

• We start from the root and go to the left subtree, then the root of the left subtree, and so on until we reach the leftmost end of the binary tree.
• If the leftmost node is a node with a right child only, the recursion goes to the right child of that node. After processing all nodes in the right subtree, the recursion backtracks to that node and processes it. Now the traversal of the leftmost node is done, and the recursion backtracks to its parent node. From here, the recursion goes to the right child of the parent node, processes all nodes in the right subtree, backtracks, and finally processes the parent node. This process continues similarly for other nodes.
• If the leftmost node is a leaf node, the recursion processes the leftmost node, and the traversal of the leftmost node is done. Now the recursion backtracks to its parent node. From here, the recursion goes to the right child, processes all nodes in the right subtree of the parent node, backtracks to the parent node, and finally processes the parent node. This process continues similarly for other nodes.

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.

Implementation Steps: Iterative Postorder Using Two Stacks

• We declare two separate stacks: rightChildStack 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. 

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.

• If the rightChildStack is not empty and the top node of the rightChildStack is equal to the right child of currNode, it means we have not yet traversed the subtree rooted at the right child. So we pop the top node from the rightChildStack and assign it to currNode.
• Otherwise, the traversal of the right subtree of currNode is done, and we can finally process currNode. After this, we pop the top node from the mainStack and update currNode with NULL (Think). In this case, the loop again goes to condition 2 and repeats the same steps until currNode is not equal to NULL.

currNode = mainStack.top()
if(!rightChildStack.isEmpty() && currNode->right == rightChildStack.top())
    currNode = rightChildStack.pop()
else 
{
    process(currNode->data)
    mainStack.pop()
    currNode = NULL
}

C++ Implementation Code

void iterativePostorder(TreeNode* root) 
{
    if (root == NULL)
        return;
        
    stack<TreeNode*> mainStack;
    stack<TreeNode*> rightChildStack;
    TreeNode* currNode = root;
    
    while (mainStack.empty() == false || 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() == false && currNode->right == rightChildStack.top()) 
            {
                currNode = rightChildStack.pop();
            } 
            else 
            {
                cout << currNode->val << " ";
                mainStack.pop();
                currNode = NULL;
            }
        }
    }
}

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

Optimized Version: Post order traversal using a single stack

Can we optimize the above idea of postorder traversal and do it using a single stack? Think! In the code below, we use a single stack to perform iterative postorder traversal and keep track of the previously visited node using the prevNode variable.

• We start by pushing the root node onto the stack and moving to its left child. We continue to push the left child until we reach a leaf node. At this point, we backtrack from the leaf node.
• While backtracking, we check if the current node has the right child and if that child has already been visited. If the right child exists and has not been visited, we move to the right child and repeat the process of pushing the left child onto the stack.
• If the right child does not exist or has already been visited, we process the current node, set it as the previously visited node, and pop the current node from the stack.

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();
            }
        }
    }
}

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 rightChildStack in the best and worst case?
• Here is an implementation code using one stack and O(n) extra memory. Does it look similar to the two-stack implementation? Think!

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();
        }
    }
}

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/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!