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