Binary Tree Preorder Traversal: Root, Left, Right

Given the root of a binary tree, return the preorder traversal of its node values. Preorder means you visit the current node first, then traverse the left subtree, then the right subtree.

This is LeetCode 144: Binary Tree Preorder Traversal. It is one of the most fundamental tree problems because it introduces the root-first processing pattern. The current node gets recorded before you recurse into its children, which makes preorder the most intuitive of the three depth-first traversal orders.

Example: given root = [1, null, 2, 3], the preorder traversal is [1, 2, 3].

Why this problem matters

Preorder traversal is one of the three standard depth-first traversal orders for binary trees (preorder, inorder, postorder). All three use the same recursive structure but differ in when the current node gets processed relative to its children.

What makes preorder useful beyond the basics is that it captures the structure of a tree from the top down. Serialization algorithms often use preorder because the root comes first, making reconstruction possible. Problems like Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105) and Verify Preorder Serialization (LeetCode 331) depend on understanding the preorder sequence.

If you can write preorder traversal from memory in both recursive and iterative forms, you have the building blocks for these harder problems.

Approach 1: Recursive

The recursive solution maps directly to the definition. Process the current node, then visit left, then visit right.

def preorder_traversal(root):
    result = []

    def dfs(node):
        if node is None:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

The base case is if node is None: return. That stops the recursion at leaves. The three lines after the base case are the entire algorithm: record the value, recurse left, recurse right. The order of those three lines is what makes it "preorder." Move result.append(node.val) between the two recursive calls and you get inorder. Move it after both and you get postorder.

Approach 2: Iterative with a stack

The iterative version replaces the call stack with an explicit stack. Interviewers sometimes ask for this form specifically, and some problems require the fine-grained control it provides.

def preorder_traversal(root):
    if root is None:
        return []
    result = []
    stack = [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

The idea: start by pushing the root onto the stack. Pop a node, immediately add its value to the result, then push its right child first, then its left child. Since a stack is last-in-first-out, pushing right before left means left gets popped (and processed) first. This preserves the root-left-right order.

Notice that preorder's iterative version is simpler than inorder's. There is no inner while loop to "go as far left as possible." You just pop, process, push children. That is because preorder processes the node the moment it is popped, without needing to defer it.

Iterative walkthrough

Let's trace the iterative approach on the example tree [1, null, 2, 3].

Each pop immediately adds the node's value to the output. The stack ensures that children get visited in the correct order: left before right. By pushing right first and left second, the left child ends up on top of the stack and gets popped next.

Complexity analysis

Time is O(n) for both approaches. Every node is visited exactly once.

Space is O(n) in the worst case for both. The recursive version uses O(h) call stack space where h is the height of the tree. The iterative version uses O(h) explicit stack space. For a balanced tree, h = log(n). For a completely skewed tree (every node only has a left child or only a right child), h = n, which gives O(n) space. Since h can be as large as n, the worst-case space for both is O(n).

Edge cases

• Empty tree (root is None): return an empty list. The recursive version hits the base case immediately. The iterative version returns early before entering the while loop.
• Single node (no children): return [root.val]. The recursive version appends the value and calls dfs(None) twice. The iterative version pops the root, adds its value, and neither child exists so nothing gets pushed. The loop ends.
• Left-skewed tree (every node only has a left child): the tree looks like a linked list going left. The iterative version pops the root, pushes the left child (no right child to push), pops that, pushes the next left, and so on. The stack never holds more than one element at a time.
• Right-skewed tree (every node only has a right child): same behavior as left-skewed but mirrored. Pop, push right child, repeat. The stack never holds more than one element.

The building blocks

This problem teaches two reusable building blocks:

1. Recursive tree traversal. The pattern of if node is None: return followed by recursive calls on node.left and node.right is the foundation of nearly every tree problem. You will use this skeleton in Maximum Depth, Path Sum, Symmetric Tree, and many others. The only thing that changes is what you do at each node and what you return.

2. Iterative stack-based traversal with root-first processing. The while stack loop with "pop, process, push children" is the iterative template for preorder. It is the simplest of the three iterative traversals because there is no deferred processing. You handle the node the moment you see it. This same pop-and-push-children pattern appears in graph BFS/DFS and in problems where you need to expand nodes in a specific order.

Both blocks are worth memorizing independently. The recursive version is simpler and should be your default. The iterative version is what you reach for when the problem demands explicit stack control.

From understanding to recall

You now understand two ways to traverse a binary tree in preorder. The recursive version is three lines inside a helper function: append, recurse left, recurse right. The iterative version is a while loop with a stack: pop, process, push right then left.

But understanding is not the same as being able to write it cold. In an interview, you will not have this post open. You need to recall the push order (right before left so left gets popped first), the immediate processing on pop, and the early return for an empty root.

Spaced repetition builds that recall. You type the solution from scratch after one day, then three days, then a week. Each time, you reconstruct the stack loop from memory. After a few rounds, the iterative preorder pattern becomes automatic. You stop thinking about it and just write it.

These two building blocks (recursive traversal and iterative stack-based traversal) appear in dozens of tree problems. Drilling them individually is far more effective than solving random tree problems and hoping the patterns stick.

Related posts

• Binary Tree Inorder Traversal - The same recursive skeleton but with left-root-right ordering, plus a different iterative approach
• Maximum Depth of Binary Tree - The best starting point for recursive tree traversal, using the same DFS skeleton