Binary Tree Preorder Traversal — Problem & Solution
Binary Tree Preorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Binary Tree Preorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees, Stack
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the values of its nodes in preorder: for every node, first the node itself, then everything in its left subtree, then everything in its right subtree.
Example 1
Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation: 1 is visited first; its only child is 2, which is visited before its own left child 3.
Example 2
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation: The whole left subtree of 1 (rooted at 2) is listed before anything in the right subtree (rooted at 3).
Example 3
Input: root = []
Output: []
Constraints
The number of nodes in the tree is in the range [0, 100]-100 <= Node.val <= 100
Follow-up: The recursive walk is short — can you do it iteratively with an explicit stack?
Hints for Binary Tree Preorder Traversal
Hint 1
Preorder records a node the moment you reach it, before either child.
Hint 2
Recursively: record the node, recurse left, recurse right. The empty subtree records nothing.
Hint 3
Iteratively, a stack serves nodes last-in-first-out — so push the right child before the left one, and the left subtree is finished first.
How to solve Binary Tree Preorder Traversal
Preorder is node, left subtree, right subtree. A stack reproduces the recursion: pop a node, record it, and push its children so that the left one comes off first.
Approach
- If the tree is empty return an empty list; otherwise push the root.
- While the stack is not empty, pop a node and append its value.
- Push its right child (if any), then its left child (if any).
- Return the list.
Why it works
The left child is pushed last, so it is popped next, and every node of its subtree is pushed above the waiting right child — the right subtree is reached only after the entire left subtree has been emptied off the stack. Each node is recorded before any of its descendants, which is the preorder rule.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion; the stack version holds at most O(h) waiting right children plus the current path
Pitfalls
- Pushing the left child first visits the right subtree first.
- Push only non-null children, or the loop has to skip nulls.
- An empty tree returns
[].
Reference solution
Python
from typing import List, Optional
def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
out = []
stack = [root] if root is not None else []
while stack:
node = stack.pop()
out.append(node.val)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return outJava
public static int[] preorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
out.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> preorderTraversal(TreeNode* root) {
vector<int> out;
vector<TreeNode*> stack;
if (root) stack.push_back(root);
while (!stack.empty()) {
TreeNode* node = stack.back();
stack.pop_back();
out.push_back(node->val);
if (node->right) stack.push_back(node->right);
if (node->left) stack.push_back(node->left);
}
return out;
}JavaScript
var preorderTraversal = function(root) {
var out = [];
var stack = root === null ? [] : [root];
while (stack.length > 0) {
var node = stack.pop();
out.push(node.val);
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals