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

There is no meaningful 'brute force vs optimal' split here. The recursive visit-then-recurse IS the natural solution. Trees skip straight to the optimal approach.

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 = height of tree

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.

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 the tree's height h. A balanced tree keeps h near log n; a completely skewed tree (a chain) pushes h to n. That's O(h): O(log n) best, O(n) worst.

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.

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