Binary Tree Preorder Traversal
Description
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Preorder traversal follows the pattern: Root → Left subtree → Right subtree. For every node in the tree, you first record the current node's value, then visit all nodes in its left subtree, and finally visit all nodes in its right subtree.
Preorder traversal is commonly used to create a copy of a tree, generate prefix expressions from expression trees, and serialize tree structures.
Examples
Example 1
Input: root = [1, null, 2, 3]
The tree looks like:
1
\
2
/
3
Output: [1, 2, 3]
Explanation: Starting from root 1, we record it first (preorder visits root before children). Then we check node 1's left child — it's null, so skip. Move to right child node 2 — record 2. Then visit node 2's left child node 3 — record 3. Node 3 has no children. Node 2 has no right child. Final: [1, 2, 3].
Example 2
Input: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]
The tree looks like:
1
/ \
2 3
/ \ \
4 5 8
/ \ /
6 7 9
Output: [1, 2, 4, 5, 6, 7, 3, 8, 9]
Explanation: Following Root-Left-Right: record 1, go left to 2 (record 2), go left to 4 (record 4, no children). Back to 2, go right to 5 (record 5), go left to 6 (record 6), back to 5, go right to 7 (record 7). Back to 1, go right to 3 (record 3, no left child), go right to 8 (record 8), go left to 9 (record 9). Result: [1, 2, 4, 5, 6, 7, 3, 8, 9].
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no nodes to visit, so the result is an empty list.
Example 4
Input: root = [1]
Output: [1]
Explanation: A single-node tree — we record the root's value and there are no subtrees to explore.
Constraints
- The number of nodes in the tree is in the range [0, 100]
- -100 ≤ Node.val ≤ 100
Editorial
Brute Force
Intuition
The most intuitive way to perform a preorder traversal is to follow its definition directly using recursion. The rule is: for any node, first record the node's own value, then recursively process its entire left subtree, then recursively process its entire right subtree.
Think of it like reading a book's table of contents. You read the chapter title first (the root), then dive into the first sub-chapter (left subtree), read all its nested sections, and only when you're completely done do you move to the second sub-chapter (right subtree).
Recursion makes this approach elegant because the system's call stack automatically remembers which nodes still need their right subtrees visited. We never need to manually track 'where to go back to' — the recursion handles it.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, null, 2, 3]
Tree structure:
1
\
2
/
3
Step 1: Call preorder(node=1). Node 1 exists. Record its value immediately → result = [1].
Step 2: Recurse into node 1's left subtree. Call preorder(node=null). Left child is null — base case, return.
Step 3: Recurse into node 1's right subtree. Call preorder(node=2). Node 2 exists. Record 2 → result = [1, 2].
Step 4: Recurse into node 2's left subtree. Call preorder(node=3). Node 3 exists. Record 3 → result = [1, 2, 3].
Step 5: Recurse into node 3's left subtree. Call preorder(node=null). Null — return.
Step 6: Recurse into node 3's right subtree. Call preorder(node=null). Null — return.
Step 7: Back at node 2. Left subtree done. Recurse into node 2's right subtree. Call preorder(node=null). Null — return.
Step 8: All calls complete. Final result = [1, 2, 3].
Recursive Preorder Traversal of [1, null, 2, 3] — Watch how preorder recursion visits the root FIRST, then dives into left and right subtrees, recording each node before exploring its children.
Algorithm
- If the current node is null, return (base case)
- Record the current node's value into the result list
- Recursively call preorder on the left child
- Recursively call preorder on the right child
- Return the result list
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(TreeNode* node, vector<int>& result) {
if (node == nullptr) return;
result.push_back(node->val);
helper(node->left, result);
helper(node->right, result);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
helper(root, result);
return result;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
def helper(node):
if node is None:
return
result.append(node.val)
helper(node.left)
helper(node.right)
helper(root)
return result/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
helper(root, result);
return result;
}
private void helper(TreeNode node, List<Integer> result) {
if (node == null) return;
result.add(node.val);
helper(node.left, result);
helper(node.right, result);
}
}Complexity Analysis
Time Complexity: O(n)
Every node is visited exactly once. At each node, we perform constant work (one append to the result list). With n total nodes, the time complexity is O(n).
Space Complexity: O(n)
The recursion call stack consumes space proportional to the height of the tree. In the worst case (a completely skewed tree — every node has only one child), the height equals n, leading to O(n) stack depth. In the best case (a balanced tree), the height is O(log n). The result list takes O(n) additional space, so total space is O(n).
Why This Approach Is Not Efficient
The recursive approach runs in optimal O(n) time, but it relies on the system's call stack for memory. For a skewed tree with many nodes, deep recursion can exhaust the system stack and cause a stack overflow error.
Every recursive call adds a frame to the call stack containing local variables, the return address, and function metadata. With n up to 100 in this problem, this isn't dangerous, but in real-world applications with trees having millions of nodes, recursion becomes a liability.
The fundamental limitation: we have no control over the system's call stack size. If we manage our own stack explicitly, we can control memory allocation better and avoid stack overflow. This motivates the iterative approach.
Better Approach - Iterative with Stack
Intuition
We can simulate the recursive preorder traversal using an explicit stack. The key observation is that in preorder, we process the current node immediately, then need to remember to visit the right subtree after finishing the left subtree.
The iterative approach works differently from the inorder iterative approach. Since we record the node BEFORE going left, we can process the current node right away. But we need to visit the left child before the right child. Since a stack is Last-In-First-Out, we push the right child FIRST, then the left child. This way, when we pop, the left child comes out first.
Think of it like a to-do list where you always work on the most recently added task. When you encounter a node: record it, then add 'visit right child' to your list, then add 'visit left child' on top. Since left was added last, you'll do it first — exactly the preorder sequence.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, null, 2, 3]
Tree:
1
\
2
/
3
Step 1: Initialize: push root (node 1) onto stack. stack = [1], result = [].
Step 2: Pop node 1. Record 1 → result = [1]. Node 1 has right child (2) — push 2. Node 1 has no left child — skip. stack = [2].
Step 3: Pop node 2. Record 2 → result = [1, 2]. Node 2 has no right child — skip. Node 2 has left child (3) — push 3. stack = [3].
Step 4: Pop node 3. Record 3 → result = [1, 2, 3]. Node 3 has no right child — skip. Node 3 has no left child — skip. stack = [].
Step 5: Stack is empty. Loop ends. Final result = [1, 2, 3].
Iterative Preorder Traversal with Explicit Stack — Watch how we pop a node, record it immediately, push right child first then left child — ensuring left is processed before right.
Algorithm
- If root is null, return empty list
- Initialize a stack and push root onto it
- While the stack is not empty:
a. Pop the top node
b. Record the popped node's value
c. If the popped node has a right child, push it onto the stack
d. If the popped node has a left child, push it onto the stack - Return the result list
Code
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
result.push_back(node->val);
// Push right first so left is processed first (LIFO)
if (node->right != nullptr) {
stk.push(node->right);
}
if (node->left != nullptr) {
stk.push(node->left);
}
}
return result;
}
};class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push right first so left is processed first (LIFO)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return resultclass Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
// Push right first so left is processed first (LIFO)
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(n)
Each node is pushed onto the stack exactly once and popped exactly once. At each pop, we do O(1) work (record value, check two children, push at most two children). Total: O(n).
Space Complexity: O(n)
The stack can hold at most O(n) nodes in the worst case. For a skewed tree (only right children), all nodes are pushed before any left child is processed. For a balanced tree, the maximum stack size is O(log n) because at most one path from root to leaf plus its siblings exists on the stack at any time. The result list takes O(n) space.
Why This Approach Is Not Efficient
The iterative stack approach gives us explicit control over memory and avoids recursion depth issues. However, it still uses O(n) auxiliary space in the worst case for the stack.
Both the recursive and iterative-stack approaches fundamentally need extra storage to remember which nodes to revisit. The stack (whether implicit via recursion or explicit) stores the 'return path' — nodes whose right subtrees haven't been explored yet.
Can we eliminate this auxiliary space entirely? Morris Traversal achieves O(1) space by temporarily modifying the tree structure itself to create 'return paths', removing the need for any stack. The idea is to use empty right pointers in the tree as temporary links back to ancestor nodes.
Optimal Approach - Morris Traversal
Intuition
Morris Traversal for preorder works similarly to Morris Inorder Traversal, but with one key difference: we record the node's value when we first visit it (before going left), not when we revisit it after completing the left subtree.
The core mechanism is the same: for each node with a left child, we find its inorder predecessor (the rightmost node in its left subtree). This predecessor's right pointer is normally null. We temporarily set it to point back to the current node, creating a 'thread' that lets us return after exploring the left subtree — all without a stack.
Here's how preorder differs from inorder in Morris Traversal:
- Morris Inorder: Record the node on the SECOND visit (when we find the thread already exists, meaning the left subtree is done)
- Morris Preorder: Record the node on the FIRST visit (when we create the thread, BEFORE going left)
For nodes without a left child, both versions behave identically: record the node and move right.
This gives us the Root-Left-Right order: we record the root before descending, traverse the entire left subtree, follow the thread back, then go right.
Step-by-Step Explanation
Let's trace through Example 1: root = [1, null, 2, 3]
Tree:
1
\
2
/
3
Step 1: Set current = node(1). Does node 1 have a left child? No. Record 1 → result = [1]. Move right: current = node(2).
Step 2: current = node(2). Does node 2 have a left child? Yes (node 3). Find the inorder predecessor: go left to 3, go as far right as possible. Node 3 has no right child (or thread), so node 3 is the predecessor.
Step 3: Does predecessor (node 3) already point back to current (node 2)? No (its right is null). This is our FIRST visit to node 2. Record 2 → result = [1, 2]. Create temporary thread: set node 3's right = node 2. Move left: current = node(3).
Step 4: current = node(3). Does node 3 have a left child? No. Record 3 → result = [1, 2, 3]. Move right: node 3's right was set to node 2 (the thread), so current = node(2).
Step 5: current = node(2) again. Does node 2 have a left child? Yes. Find predecessor: go left to 3, go right... node 3's right points to node 2 (current). This means we've already visited this node (second visit).
Step 6: Remove the thread: set node 3's right = null (restore tree). Do NOT record node 2 again. Move right: current = node(2).right = null.
Step 7: current = null. Loop ends. Final result = [1, 2, 3].
Morris Preorder Traversal — O(1) Space — Watch how Morris Preorder records nodes on the FIRST visit (before creating threads and going left), achieving Root-Left-Right order with O(1) space.
Algorithm
- Set current = root
- While current is not null:
a. If current has no left child:- Record current's value
- Move to current's right child
b. If current has a left child: - Find the inorder predecessor (rightmost node in left subtree)
- If predecessor's right is null (first visit):
- Record current's value (preorder: visit root BEFORE left subtree)
- Set predecessor's right = current (create temporary link)
- Move current to its left child
- If predecessor's right == current (second visit):
- Set predecessor's right = null (remove temporary link, restore tree)
- Do NOT record (already recorded on first visit)
- Move current to its right child
- Return the result list
Code
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
TreeNode* current = root;
while (current != nullptr) {
if (current->left == nullptr) {
// No left subtree: visit current, go right
result.push_back(current->val);
current = current->right;
} else {
// Find inorder predecessor
TreeNode* predecessor = current->left;
while (predecessor->right != nullptr && predecessor->right != current) {
predecessor = predecessor->right;
}
if (predecessor->right == nullptr) {
// First visit: record current, create thread, go left
result.push_back(current->val);
predecessor->right = current;
current = current->left;
} else {
// Second visit: remove thread, go right (already recorded)
predecessor->right = nullptr;
current = current->right;
}
}
}
return result;
}
};class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
current = root
while current is not None:
if current.left is None:
# No left subtree: visit current, go right
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right is not None and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
# First visit: record current, create thread, go left
result.append(current.val)
predecessor.right = current
current = current.left
else:
# Second visit: remove thread, go right (already recorded)
predecessor.right = None
current = current.right
return resultclass Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// No left subtree: visit current, go right
result.add(current.val);
current = current.right;
} else {
// Find inorder predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// First visit: record current, create thread, go left
result.add(current.val);
predecessor.right = current;
current = current.left;
} else {
// Second visit: remove thread, go right (already recorded)
predecessor.right = null;
current = current.right;
}
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(n)
Although finding the predecessor involves traversing part of the tree, each edge is visited at most three times across the entire algorithm (once going down, once for thread creation, once for thread removal). With n-1 edges in a tree with n nodes, the total extra work is O(n). Combined with the main loop visiting each node at most twice (once for first visit, once for second visit when a thread is found), the overall time is O(n).
Space Complexity: O(1)
Morris Traversal uses only two pointer variables (current and predecessor) regardless of tree size. No stack, no recursion. The tree is temporarily modified with threads but fully restored by the end. The result list takes O(n) but is required output — the auxiliary space is genuinely O(1).
This makes Morris Traversal the most space-efficient approach for preorder traversal.