Binary Tree Preorder Traversal — Solution

Problem

Given the root of a binary tree, return a list of every node's value collected in preorder — that is, visit the root first, then fully traverse the left subtree, then the right subtree.

[1,2,3,4,5]

• Input: root = [1, 2, 3, 4, 5]
• Output: [1, 2, 4, 5, 3]
• Explanation: Starting at 1, we go left to 2's entire subtree (2 → 4 → 5) before crossing over to the right child 3.

Intuition

Preorder is the most natural DFS order — "pre" means the root is recorded before its descendants. Because the structure is self-similar (each subtree is itself a tree), a recursive function that mirrors the definition works directly: record the current node, then repeat the same process on the left child, then the right child.

Solution — Recursive DFS

Append the current node's value to a shared result list, then recurse on the left child, then the right child. An inner function keeps the result list in scope without passing it as a parameter.

Steps:

1. If the current node is null, return immediately — nothing to visit.
2. Append the current node's value to the result list (root before its descendants).
3. Recursively visit the left subtree.
4. Recursively visit the right subtree.
5. After the initial call returns, return the completed result list.

1class Solution:
2    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3        result = []
4
5        def dfs(node):
6            if not node:
7                return
8            result.append(node.val)  # root recorded before its descendants
9            dfs(node.left)
10            dfs(node.right)
11
12        dfs(root)
13        return result

• Time: O(n) — every node is visited exactly once
• Space: O(h) — recursion stack is one frame deep per level; O(log n) for a balanced tree, O(n) worst case for a fully skewed tree

Complexity Summary

Common Mistakes

• Confusing the three DFS orders: preorder is root → left → right; inorder is left → root → right; postorder is left → right → root. A mnemonic: the "pre/in/post" prefix tells you where the root goes — before, between, or after its subtrees.
• Adding the value after the recursive calls: placing result.append(node.val) after dfs(node.left) and dfs(node.right) produces postorder, not preorder — the append must come first.
• Using + concatenation in a loop: return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right) works but allocates O(n) intermediate lists. Appending to a single shared list is significantly more efficient.
• Assuming preorder output matches the BFS input array: the preorder output of [1, 2, 3, 4, 5] (BFS) is [1, 2, 4, 5, 3], not [1, 2, 3, 4, 5] — the entire left subtree of 2 (nodes 4 and 5) is visited before moving to 3.
• Missing the null check before accessing children: calling dfs(node.left) without first checking if not node will raise a NoneType error when a leaf's child is null — always guard with a base case at the top of the function.

Related Problems

• binary-tree-inorder-traversal — same recursive structure, just move result.append between the two recursive calls instead of before them
• binary-tree-postorder-traversal — same recursive structure, just move result.append after both recursive calls
• binary-tree-level-order-traversal — BFS alternative that collects nodes layer by layer rather than depth-first
• construct-binary-tree-from-preorder-and-inorder-traversal — uses preorder output as input; understanding preorder order is a prerequisite
• binary-tree-zigzag-level-order-traversal — contrasts BFS with direction alternation against DFS approaches like preorder