Binary Tree Preorder Traversal: Root, Left, Right Explained
Learn binary tree preorder traversal with recursive JavaScript DFS, a worked trace, complexity analysis, and the root-left-right pattern.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Preorder traversal is the tree walk to reach for when a node must be handled before anything beneath it. The rule is tiny — root, then left, then right — but the timing is what matters. The parent is recorded as soon as the recursive call reaches it, so the output describes a top-down exploration.
That order is useful whenever the root carries information that should appear before its descendants: serializing a tree, copying it, producing a prefix-style representation, or simply making a DFS trace easy to read. Recursion is a particularly good fit because a binary tree is already defined as a node with two smaller binary trees.
The problem
Given the root of a binary tree, return the values in preorder: visit the current node, traverse its left subtree, then traverse its right subtree. A missing child is represented by null and contributes no value.
Tree: 1
\
2
/
3
Output: [1, 2, 3]The level-order input [1, null, 2, 3] can look misleading at first: node 3 is the left child of 2, not a sibling of 1. Preorder does not care how the tree was encoded. It follows actual child pointers, recording a node before recursing into either child.
The brute force baseline
There is no useful nested-loop baseline for a traversal. A list of values is not enough to recover a tree's shape, and repeatedly searching that list for each node would add work without helping the visit order. The honest baseline is a manual DFS: keep an explicit list of nodes still to visit, take a node, record it, then arrange for its children to be processed in preorder.
function preorderWithWorklist(root) {
if (!root) return [];
const result = [];
const work = [root];
while (work.length) {
const node = work.shift();
result.push(node.val);
if (node.left) work.push(node.left);
if (node.right) work.push(node.right);
}
return result;
}This code is wrong for preorder: removing from the front and appending children performs breadth-first traversal instead. Switching shift() to pop() makes it depth-first, but then pushing the children in the natural left-then-right order still visits right first because a stack is last-in, first-out. The baseline exposes the core issue: the data structure and insertion order determine traversal order.
The key insight: do the work on entry
Each recursive dfs(node) call owns exactly one subtree. If node is null, that subtree has no work. Otherwise, the call has three obligations in a fixed order:
- Record
node.valimmediately. - Finish the complete left subtree.
- Finish the complete right subtree.
The word pre in preorder means the record step comes before the recursive child calls. This is the only difference from inorder and postorder, yet it changes the result completely. The JavaScript call stack preserves the unfinished right-subtree obligation while the left subtree runs, then returns to it automatically.
The optimal solution
The visualizer's canonical solution uses a result array and a nested DFS. It does not construct another tree or maintain an explicit stack; JavaScript's call stack is the stack.
function preorderTraversal(root) {
const result = [];
function dfs(node) {
if (!node) return;
result.push(node.val);
dfs(node.left);
dfs(node.right);
}
dfs(root);
return result;
}The base case must be the first statement inside dfs. It makes leaf children harmless: calling dfs(null) returns instead of trying to access null.val. For every real node, result.push(node.val) happens before either child call. Once dfs(node.left) returns, every value in that left subtree has already been appended; only then can dfs(node.right) append values from the right subtree.
You can step through it interactively and watch the result array change at the exact moment each recursive frame enters a node.
Walkthrough: [1, 2, 3, 4, 5, null, 6]
This level-order input represents a tree with 1 at the root; 2 and 3 below it; 4 and 5 below 2; and 6 as the right child of 3. The traversal must finish the entire left side of 1 before it begins node 3.
| Step | Active call | Operation | result |
|---|---|---|---|
| 1 | dfs(1) | Push root before children | [1] |
| 2 | dfs(2) | Enter left subtree; push 2 | [1, 2] |
| 3 | dfs(4) | Push 4; both child calls return | [1, 2, 4] |
| 4 | dfs(5) | Return to 2, then push its right child | [1, 2, 4, 5] |
| 5 | dfs(3) | Left subtree of 1 is complete; push 3 | [1, 2, 4, 5, 3] |
| 6 | dfs(6) | Null left child returns; push right child | [1, 2, 4, 5, 3, 6] |
Notice that a null child never appears in result; it only triggers the base case. Also notice why 3 follows 5, even though it is a child of the root: the call to dfs(2) must finish before dfs(3) begins.
Complexity
| Approach | Time | Extra space | Why |
|---|---|---|---|
| Queue-based level order | O(n) | O(n) | Visits every node, but produces the wrong order for preorder |
| Recursive preorder DFS | O(n) | O(h) | Each node is pushed once; at most the tree height is active |
| Explicit-stack preorder DFS | O(n) | O(h) | Same traversal, with the pending path stored manually |
Here n is the number of nodes and h is tree height. The output array itself uses O(n) space because returning n values requires n slots. The O(h) figure is auxiliary traversal space: O(log n) for a balanced tree and O(n) for a completely skewed one.
Common mistakes
- Putting
result.pushafter the left call. That silently turns the solution into inorder traversal. - Forgetting the null base case. Every leaf recursively reaches two null children; without the guard, the next access throws.
- Assuming preorder sorts values. It is an order of visiting structure, not values. Only inorder on a valid BST has the sorted-output property.
- Mixing up iterative push order. With an explicit stack, push the right child first and the left child second, so the left child is popped first.
- Calling recursion O(1) space. The result array and the call stack both consume memory; the latter can grow to O(n) on a chain.
Where this pattern shows up next
Preorder is one member of a family; change when the node value is appended and you get a different traversal with different uses.
The iterative preorder variant uses the same root-left-right behavior with a stack you control. Iterative inorder makes deferred nodes explicit, while postorder visits both children before the parent and therefore fits bottom-up calculations. A two-stack postorder implementation makes that child-before-parent schedule especially visible.
Those variants are worth comparing after the recursive version feels automatic. Do not memorize three unrelated templates: identify whether the parent is processed before its children, between them, or after them. Then the code order follows directly from the desired output order.
FAQ
What is preorder traversal in a binary tree?
Preorder traversal visits the current node first, then every node in its left subtree, then every node in its right subtree. For a root 1 with children 2 and 3, the order starts [1, 2, 3].
Why is preorder called root-left-right?
That phrase names the three operations of each recursive call: process the root before making recursive calls, complete the left subtree, then complete the right subtree. The placement of the processing step before both calls is what makes it preorder.
Is recursive preorder traversal O(n) time?
Yes. Every non-null node enters dfs once and is appended once, so the work grows linearly with the number of nodes. Null calls are bounded by the tree's child pointers and do not change the O(n) result.
When should I prefer iterative preorder traversal?
Use an explicit stack when input trees may be so deep that recursive calls risk exceeding the JavaScript call-stack limit, or when you need precise control over pausing and resuming the traversal. The iterative algorithm still needs O(h) pending-node space in the typical depth-first case.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.