Binary Tree Preorder Traversal

Intuition

The recursive form is trivial (record node, recurse left, recurse right), but we can convert it into an iterative loop with a single explicit stack. A stack is last-in-first-out, so if we want the left child processed before the right child, we must push the right child first and the left child second. Then each iteration pops a node, records it immediately (satisfying the node-first rule), and schedules its children. This guarantees that whenever we pop, we are always looking at the next node in preorder.

Algorithm walkthrough

1. 1Return an empty list right away if the root is null.
2. 2Initialize a stack containing only the root node.
3. 3While the stack is not empty, pop the top node and append its value to the result.
4. 4Push the node's right child if it exists so it is handled after the left branch.
5. 5Push the node's left child if it exists so it is popped and handled next.
6. 6Continue until the stack empties, then return the collected values.

Implementation

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result: List[int] = []
        stack: List[TreeNode] = [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result