Binary Tree Preorder Traversal

Difficulty: Easy Source: NeetCode

Problem

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1: Input: root = [1,null,2,3] Output: [1,2,3]

Example 2: Input: root = [] Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary Trees — Hierarchical data structure where each node has at most two children
• Recursion — Solving a problem by breaking it into the same problem on smaller inputs
• Stack — LIFO structure that lets us control the visit order iteratively

1. Recursive DFS

Intuition

Preorder means root → left → right. You visit the current node first, then explore left, then right. This is the most natural traversal for printing or copying a tree because you process a node before its subtrees.

Algorithm

1. If the current node is null, return
2. Append the current node’s value to the result
3. Recurse on the left child
4. Recurse on the right child

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_recursive(root):
    result = []

    def dfs(node):
        if not node:
            return
        result.append(node.val)  # Visit root first
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, None, 2, 3])
print(preorder_recursive(root1))  # [1, 2, 3]

root2 = build_tree([])
print(preorder_recursive(root2))  # []

root3 = build_tree([1, 2, 3, 4, 5])
print(preorder_recursive(root3))  # [1, 2, 4, 5, 3]

Complexity

• Time: O(n) — every node is visited exactly once
• Space: O(h) — recursion depth equals tree height

2. Iterative (Stack-Based)

Intuition

For preorder, we want to visit root first, then left before right. With a stack, we can achieve this by pushing the right child before the left child — since the stack is LIFO, left gets processed first.

Algorithm

1. Initialize a stack with the root node
2. While the stack is not empty:
   • Pop a node and record its value
   • Push the right child first (so left is processed first)
   • Push the left child

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, None, 2, 3])
print(preorder_iterative(root1))  # [1, 2, 3]

root2 = build_tree([])
print(preorder_iterative(root2))  # []

root3 = build_tree([1, 2, 3, 4, 5])
print(preorder_iterative(root3))  # [1, 2, 4, 5, 3]

Complexity

• Time: O(n) — every node is pushed and popped once
• Space: O(h) — stack holds at most one path worth of nodes at a time

Common Pitfalls

Pushing children in the wrong order. In the iterative approach, you must push right before left. It feels backwards, but since the stack is LIFO, left will be popped (and processed) first — which is exactly what preorder needs.

Off-by-one with null checks. Only push a child if it actually exists. Pushing None onto the stack will cause a crash when you try to access .val on it.