Binary Tree Preorder Traversal
The key idea
Preorder means root, then left subtree, then right subtree. Apply that same rule at every node: emit the node's value the moment you arrive, before you descend. The recursion mirrors the definition exactly, and an explicit stack reproduces it by pushing the right child before the left so the left pops first.
Problem
Given the root of a binary tree, return the preorder traversal of its nodes' values.
In a preorder traversal you visit each node in the order root, then the entire left subtree, then the entire right subtree, applying the same rule recursively at every node.
Follow-up: the recursive solution is trivial — could you do it iteratively instead?
Constraints
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Examples
Input: root = [1,null,2,3]
Output: [1,2,3]
Input: root = []
Output: []
Input: root = [1]
Output: [1]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM