Binary Tree Preorder Traversal

Difficulty: Easy

Problem

Given the root of a binary tree, return the preorder traversal of its nodes' values. Preorder visits nodes in Root → Left → Right order: record the node itself FIRST, then its entire left subtree, then its entire right subtree.

Example

Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation: Arrive at 1 and visit it immediately. Its left child is null, so go right to 2 — visit 2 on arrival. Then go to 2's left child 3 and visit 3. Result: [1,2,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