Binary Tree Preorder Traversal

Difficulty: Easy

Problem

Take the root of a binary tree and return its values in preorder: write down the current node right away, then walk its whole left subtree, then its whole right subtree.

Example

Input: root = [1,2,3,4,5]
Output: [1,2,4,5,3]
Explanation: Record 1 on arrival, move into the left child 2 and record it, then its children 4 and 5 in turn. Finally return to the right child 3 of the root: [1,2,4,5,3].

Brute-force approach

The first idea is a plain loop with no memory: stand on the root, record it, step to the left child, record it, and keep stepping left. It stops at the first empty spot and has no way back, so it forgets every node it walked past on the way down. On [1,2,3,4,5] it records 1, 2, 4 and stops: 3 of the 5 nodes (5 and 3 are lost). The fix is memory of what is still waiting: the call stack in the recursive version, an explicit stack in the iterative one.

Steps

  1. Start at the root; record its value
  2. Step to the left child and record it; repeat until there is no left child
  3. Stop: the loop has nowhere to go back to, so every right child it passed is never visited (3 of 5 nodes on the example)
  4. Repair: remember the pending right children (recursion, or a stack) and come back to them

Time complexity: O(n) but wrong: it only reaches the left spine · Space complexity: O(1) but wrong

Trade-offs

  • Forgets the nodes it left behind: records [1, 2, 4] instead of [1, 2, 4, 5, 3]
  • Needs memory for the pending right children, which is exactly what the recursion or the explicit stack provides

Optimal approach

Key insight: The only difference from inorder is WHERE the visit happens. Preorder appends node.val as the very first action on arrival. Move one line up, and you get a whole new traversal.

Walk the tree with DFS, recording each node's value the moment you arrive, BEFORE recursing into the left subtree, then the right. The result list fills itself in Root → Left → Right order.

Steps

  1. Create an empty result list
  2. Base case: if the node is null, return
  3. Visit: append node.val the moment you arrive
  4. Recurse into the left subtree, then the right subtree
  5. Kick off at the root and return result

Time complexity: O(n) · Space complexity: O(h) where h = the number of levels (the tree's maximum depth)

Pseudocode

function preorderTraversal(root):
    result = []
    
    function preorder(node):
        if node is ____:
            return
        
        ____                       // the visit: why does it come FIRST?
        preorder(node.____)        // which child first?
        preorder(node.____)        // which child second?
    
    preorder(root)
    return result

Hints

  • Base case: what value means 'empty spot, nothing to record here'?
  • The visit is result.append(node.val), and in PREorder it is the very FIRST action after the base case, before any recursive call
  • Root → LEFT → Right: recurse into the left child before the right one
  • Compare with inorder: only the position of the append line changed. The skeleton never changes.
  • The outer function is preorderTraversal and the inner helper is preorder: they differ by two letters, so check that the helper is the one you call recursively.
  • Memory trick: pre, in, post = the root BEFORE, BETWEEN, AFTER its two sides.
  • Iterative version: the stack gives back the last node pushed, so push the RIGHT child first and the left child second. Guard the empty tree first (if root is None: return []).

Complexity questions

What is the time complexity of preorder traversal on a tree with n nodes?

O(n). Every node is visited exactly once, and each visit does O(1) work. One append and two recursive calls. n nodes × O(1) each = O(n).

Ignoring the output list, what is the space complexity of the recursive solution?

O(h): the call stack grows to the tree's height. The recursion stack holds one frame per level of depth, so it grows to about the tree's height h (the number of levels; the peak is h + 1 counting the call on an empty spot). A balanced tree keeps h near log n; a completely skewed tree (a chain) pushes h to n, and Python stops the recursion near 1,000 nested calls. That's O(h): O(log n) best, O(n) worst. The explicit-stack version holds at most h nodes, and only 1 on a chain.

For the SAME tree, do preorder and inorder visit the same set of nodes?

Yes: same n nodes, same O(n) cost; only the ORDER of visits differs. Both traversals reach every node exactly once, so both cost O(n) time and O(h) stack. The only thing that changes is WHEN each node gets recorded, on arrival for preorder, after the left subtree for inorder.

You need to make a deep copy of a tree. Which traversal fits best, and why?

Preorder: each parent is created before its children, so there is always a node to attach to. To attach a child, its parent must already exist. Preorder hands you every parent before its children: copy the node on arrival, then recurse to build its left and right. This is also why tree serialization formats use preorder.

In the explicit-stack version, which child is pushed FIRST so that the left subtree is still visited before the right?

The right child: a stack gives back the last node pushed, so the left child pops first. A stack returns the last node pushed. To visit the left child first, push the right child first and the left child second. Flip the two pushes and the walk visits the right side first: [1, 3, 2, 5, 4] on the example. Guard the empty tree first (return [] when root is None).

Check your understanding of Binary Tree Preorder Traversal

In what order does a preorder traversal visit the parts of a tree?

Root → Left → Right. 'Pre' means the root comes BEFORE its subtrees: Root → Left → Right. Left-Root-Right is inorder, Left-Right-Root is postorder, and level-by-level is BFS, four traversals, four different orders.

What does preorder traversal return for the tree [1,null,2,3] (root 1, no left child, right child 2, and 3 is 2's left child)?

[1,2,3]. Visit 1 the moment we arrive. Left is null, so go right to 2 and visit it, then down to 2's left child 3. Answer: [1,2,3]. If you picked [1,3,2], you traced INORDER. That's what you get by letting the left side finish before visiting the node.

WHEN exactly is a node visited in preorder?

The instant you arrive at it, before touching either child. Preorder visits on ARRIVAL: the node records itself first, then recurses left, then right. Compare: inorder visits after the left side finishes, and postorder visits on departure, after both children are done.

What is preorder's superpower, its classic use case?

Copying or serializing a tree: parents come out before their children. To rebuild a tree you must create each parent before you can attach its children. Preorder hands you nodes in exactly that order, which is why copy and serialize routines use it. Sorted BST output is inorder's trick, and leaf-first deletion is postorder's.

Preorder on [4,2,7,1,3,6,9] starts 4, 2, 1, 3, ..., once node 2's subtree is completely finished, which node is visited next?

7: return to root 4 and enter its RIGHT subtree. When 2's subtree (2, 1, 3) is done, control returns to root 4. But 4 already spoke on arrival. Its only remaining job is preorder(right), so we arrive at 7 and record it immediately. Full order: [4,2,1,3,7,6,9].

Related problems

Keep practising