Preorder Traversal

Binary tree preorder traversal visits nodes in a specific order: root, then its left subtree, then its right subtree. While often implemented recursively, an iterative approach using an explicit stack offers an alternative, avoiding potential stack overflow issues with deep trees.

How It Works

This iterative method simulates the call stack of a recursive traversal. It ensures that the root is processed first, followed by its left child, and then its right child, by carefully managing the order in which children are pushed onto the stack.

Initialize the Stack

Begin by creating an empty list to store the traversal result and an explicit stack. Push the root node onto the stack to initiate the process. If the tree is empty, the result will be an empty list.

Process Nodes Iteratively

The core of the algorithm involves a loop that continues as long as the stack is not empty. In each iteration:

1. Pop and Visit: Remove the top node from the stack. This node is the current root of the subtree being processed. Add its value to your result list. 2. Push Children: Crucially, push the current node's children onto the stack. Push the *right* child first, then the *left* child. This order ensures that when nodes are popped later, the left child will be processed before the right child, adhering to the preorder sequence.

Repeat this process until the stack is empty, at which point all nodes will have been visited in preorder.

def preorder(root):
    if not root: return []
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

Key Takeaways

• Preorder traversal visits nodes in the order: root, left, right.
• An explicit stack can replace recursion for iterative traversal.
• Push the right child before the left child to maintain preorder sequence.
• The algorithm processes nodes by popping from the stack and then pushing their children.
• This method avoids recursion depth limits for very deep trees.