Binary Tree Preorder Traversal
Binary Tree Preorder Traversal is LeetCode 144 (Easy). Given the root of a binary tree, return its node values in preorder: the node, then its left subtree, then its right subtree.
- The tree can be empty; then the answer is
[]. - Follow-up: the recursive solution is trivial, so do it iteratively.
With at most 100 nodes any O(n) walk is fast; the point is to replace the recursion with a stack you manage yourself.
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Intuition
In a binary tree preorder traversal a node is output as soon as it is reached, before anything below it. So an iterative preorder traversal only has to track which subtrees are still waiting, and a stack does that: pop a node, record it, push its children.
The one twist is the order. A stack returns the last item pushed, so the children go in right first, left second. The left subtree is then finished before the right one starts, giving node, left, right.
Preorder is the order to use when a node must be handled before its children: copying or serialising a tree, printing a folder hierarchy, or passing a value down from parent to child. Serialize and Deserialize Binary Tree, Flatten Binary Tree to Linked List and Construct Binary Tree from Preorder and Inorder Traversal all rely on the root coming first.
Approach
Before reading on: for the tree [1,2,3,4,5], the answer is [1, 2, 4, 5, 3]. After you output 1, both 2 and 3 are waiting. If you keep them on a stack, in which order must you push them so that 2 comes out first?
Two ways to solve it
Pop a node, record it, then push its right child and its left child.
- Follow-up: the iterative answer LeetCode asks for.
- Depth: no recursion limit on a chain-shaped tree.
- Shape: the simplest of the three iterative orders.
The version to know for interviews.
A helper appends the node, then recurses left and right.
- Code: three lines that mirror the definition.
- Memory: the call stack holds one path.
- Limit: a very deep tree can hit the recursion limit.
Fine when recursion is allowed and the tree is shallow.
Both visit each node once in O(h) memory, but the stack version answers the follow-up and has no recursion-depth limit, so the steps, code and live demo follow it. The recursive code comes after the demo.
Return early for an empty tree
If root is empty, return []. Otherwise start the stack with the root. Each node on the stack stands for a whole subtree still to visit, so the stack never holds an empty node.
Pop and record
Pop the top node and append its value straight away. A node comes before its children in preorder, so there is nothing to wait for: the moment it leaves the stack is its place in the answer.
Push right, then left
Push the node's children, skipping empty ones:
- the right child first;
- the left child second, so it is on top.
The stack returns the last item pushed, so the left subtree is finished before the right child is popped.
Stop when the stack is empty
An empty stack means no subtree is left. Each node is pushed once and popped once, so the walk is O(n) time; the stack holds O(h) nodes for a typical tree and never more than n.
Binary Tree Preorder Traversal solution in Python | C++ | Java
.val from nothing.Recursive preorder traversal
dfs(node) returns at once on an empty node; otherwise it appends node.val, then visits the left subtree, then the right subtree. The call stack keeps track of where to return.
Common pitfalls
Pushing the left child first
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)The stack returns the last child pushed, so the right subtree would be visited before the left. For [1,2,3] the answer comes out [1, 3, 2] instead of [1, 2, 3].
Pushing empty children
stack.append(node.right) stack.append(node.left)
if node.right:
stack.append(node.right)In Python a later pop returns None and node.val crashes. In a binary tree preorder traversal Java version, ArrayDeque.push(null) throws a NullPointerException at once. Check each child before pushing it.
Recording the node after its children
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
result.append(node.val)def dfs(node):
if not node:
return
result.append(node.val)
dfs(node.left)
dfs(node.right)Where the append sits is the only difference between the depth-first orders. After both calls it is postorder; for [1,2,3] that gives [2, 3, 1].
Complexity
Binary Tree Preorder Traversal FAQ
Can LeetCode 144 be solved in O(1) extra space?
Yes, with Morris traversal. It records a node, then links the rightmost node of its left subtree back to it, so the walk can climb back up without a stack. The links are removed on the way back. Time stays O(n).