Inorder Traversal

Binary tree inorder traversal visits nodes in a specific left-root-right order. While recursion provides a concise solution, an iterative approach using an explicit stack offers a deeper understanding of how the tree is navigated and how backtracking occurs.

How Iterative Inorder Traversal Works

The iterative inorder traversal uses a stack to keep track of parent nodes as it descends the tree and manage the order of processing. The core idea is to always prioritize visiting the leftmost node first, then the current node, and finally its right subtree.

Descending Left

Starting from the root, the algorithm repeatedly pushes the current node onto a stack and moves to its left child. This continues until a null left child is encountered, indicating the deepest leftmost node in the current path has been reached.

Visiting and Backtracking

Once a null left child is found, the algorithm pops the top node from the stack. This popped node is the next one to be visited in inorder sequence. After visiting, the algorithm then attempts to move to the right child of the just-visited node. If a right child exists, the process of descending left from this new node begins again. If there is no right child, the algorithm continues popping from the stack, effectively backtracking up the tree until a node with an unprocessed right child (or the root) is found.

This cycle of pushing nodes while moving left, popping and visiting, then moving right, continues until both the current node pointer is null and the stack is empty, signifying that all nodes have been visited.

def inorder(root):
    res, stack = [], []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right
    return res

Key Takeaways

• Inorder traversal visits nodes in left-root-right sequence.
• An explicit stack manages the traversal state, simulating the call stack of recursion.
• Nodes are pushed onto the stack as the algorithm descends left.
• Nodes are popped and visited when a null left child is encountered.
• After visiting a node, the algorithm attempts to traverse its right subtree.