Iterative In-order Traversal

Category

Binary Trees

Difficulty

Hard

Problem Statement

Write a function that performs an in-order traversal of a binary tree iteratively (without using recursion). In-order traversal visits nodes in the order: left subtree, current node, right subtree. The function should call a given callback function on each node as it is visited. The tree nodes have a parent pointer in addition to left and right pointers.

Intuition

The recursive in-order traversal uses the call stack to remember where to return after processing a subtree. Iteratively, we must manage this ourselves. With parent pointers available, we can determine where we came from at each step and decide what to do next: if we came from the parent, go left; if we came from the left child, process the current node and go right; if we came from the right child, go back up. This state machine approach eliminates the need for an explicit stack.

Approach

1. Start at the root with previousNode = null and currentNode = root.
2. While currentNode is not null: a. If previousNode is currentNode.parent (or previousNode is null for the root): we arrived from above, so try to go left. If left child exists, move to it. Otherwise, process the current node and try to go right. If right child also does not exist, move back up to parent. b. If previousNode is currentNode.left: we returned from the left subtree, so process the current node. Then try to go right. If no right child, move back up to parent. c. If previousNode is currentNode.right: we returned from the right subtree, so move back up to parent.
3. Update previousNode and currentNode accordingly at each step.

Pseudocode

function iterativeInOrderTraversal(tree, callback):
    previousNode = null
    currentNode = tree

    while currentNode is not null:
        if previousNode == currentNode.parent:
            // Came from parent, go left first
            if currentNode.left is not null:
                nextNode = currentNode.left
            else:
                callback(currentNode)
                if currentNode.right is not null:
                    nextNode = currentNode.right
                else:
                    nextNode = currentNode.parent

        else if previousNode == currentNode.left:
            // Came from left child, process current then go right
            callback(currentNode)
            if currentNode.right is not null:
                nextNode = currentNode.right
            else:
                nextNode = currentNode.parent

        else:  // previousNode == currentNode.right
            // Came from right child, go back up
            nextNode = currentNode.parent

        previousNode = currentNode
        currentNode = nextNode

Time & Space Complexity

• Time: O(n) where n is the number of nodes. Each node is visited a constant number of times (entered from parent, returned to from left child, returned to from right child).
• Space: O(1) auxiliary space. No stack or queue is used. The parent pointers are part of the tree structure.

Key Insights

• The parent pointer is what makes O(1) space possible. Without it, an explicit stack of O(h) space is needed.
• The algorithm is essentially a state machine with three states based on where we came from.
• For the root node, previousNode is null, which we treat the same as coming from the parent.
• This approach processes each edge exactly twice (once going down, once going up), confirming the O(n) time.
• An alternative iterative approach without parent pointers uses an explicit stack: push nodes while going left, pop to process, then move to the right child.

Edge Cases

• The tree is null/empty — the while loop never executes.
• The tree has only a root node — process it and finish (no left or right).
• The tree is entirely left-skewed — traversal goes all the way down, then processes nodes bottom-up.
• The tree is entirely right-skewed — each node is processed immediately before moving right.
• The callback modifies the tree — behavior is undefined and should be avoided.