[LeetCode] 144. Binary Tree Preorder Traversal

🧠 Remember: “Preorder → write it down FIRST, then go left, then go right.”

The problem — 20 seconds

root = [1,null,2,3] → [1,2,3].

Record the node, then the left subtree, then the right subtree.

visit 1 → [1] · left empty · go right
visit 2 → [1, 2] · go left
visit 3 → [1, 2, 3] · done

That trace is the entire algorithm. The only real question is where the recording line sits.

Your first instinct

Recursion writes itself — the skeleton is three lines, and the follow-up (“could you do it iteratively?”) is the actual interview question:

dfs(node): visit(node) → dfs(left) → dfs(right)

Recursion borrows the call stack; iteration simulates it by hand.

The turning point

Preorder, inorder, and postorder share one skeleton. The only difference is the position of visit: first here, in the middle for inorder, last for postorder. Memorize positions, not three algorithms.

Watch it work

Press Play. On the shared tree the badges land 1st → 5th as [1, 2, 4, 5, 3]: node first, dive left, then swing right.

Interactive visual · Preorder walk

Node first, then children — can you feel the order?

Preorder records each node BEFORE its children: visit 1, dive left (2, 4, 5), then swing right (3). Watch the badges land 1st → 5th.

current recorded not yet

output

Step 1 / 7 Speed

·def traverse(node):

1traverse(node.left) # left subtree

2visit(node) → output # record value

3traverse(node.right) # right subtree

Quick check — make it stick

When is the node itself recorded?

🧠 Memory hook: “PRE = node first · IN = node in the middle · POST = node last.”

The code, for real

Recursive primary — the recording line sits first:

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
        self.val, self.left, self.right = val, left, right

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        out: list[int] = []
        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return
            out.append(node.val)  # visit FIRST
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return out

Iterative secondary — pop, record, then push right before left so left pops first:

from typing import Optional

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

Why it works

Invariant: every node enters out exactly once, at the moment it is visited, so out is always the preorder prefix recorded so far.

n = 1,000 → ~1,000 visits · stack depth = tree height
Time O(n), space O(h).

🧠 Remember

Preorder → “node FIRST.” visit before both children — that single position is the whole difference from inorder and postorder.

🔁 Try this: recite root = [1,null,2,3] from memory, then compare with the other two.