Tree Traversal
Learn the four ways to visit every node in a tree — preorder, inorder, postorder, and level-order.
Tree Traversal
Traversal means visiting every node in a tree exactly once. Unlike arrays, which have one natural order, trees support multiple valid orders depending on when you process the current node relative to its children.
1
/ \
2 3
/ \
4 5visited order
The three depth-first orders
All three follow the same recursive shape — only the position of "visit node" changes relative to the recursive calls.
Preorder — node, left, right
def preorder(node, result=None):
if result is None:
result = []
if node:
result.append(node.value) # visit BEFORE children
preorder(node.left, result)
preorder(node.right, result)
return result
# tree above → [1, 2, 4, 5, 3]Use case — copying a tree, or generating a prefix expression from an expression tree.
Inorder — left, node, right
def inorder(node, result=None):
if result is None:
result = []
if node:
inorder(node.left, result)
result.append(node.value) # visit BETWEEN children
inorder(node.right, result)
return result
# tree above → [4, 2, 5, 1, 3]Use case — on a binary search tree, inorder traversal visits nodes in sorted order. This is the most common reason to use inorder.
Postorder — left, right, node
def postorder(node, result=None):
if result is None:
result = []
if node:
postorder(node.left, result)
postorder(node.right, result)
result.append(node.value) # visit AFTER children
return result
# tree above → [4, 5, 2, 3, 1]Use case — deleting a tree (children must be freed before the parent), or evaluating an expression tree (operands before operators).
Level-order — breadth-first
Visits nodes level by level, left to right. Unlike the other three, this is not recursive by nature — it uses a queue.
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# tree above → [1, 2, 3, 4, 5]Use case — finding the shortest path in an unweighted tree, printing a tree level by level, or any "closest first" exploration.
All four orders, side by side
1
/ \
2 3
/ \
4 5| Order | Result | Pattern |
|---|---|---|
| Preorder | [1, 2, 4, 5, 3] | node → left → right |
| Inorder | [4, 2, 5, 1, 3] | left → node → right |
| Postorder | [4, 5, 2, 3, 1] | left → right → node |
| Level-order | [1, 2, 3, 4, 5] | level by level |
Iterative versions — using an explicit stack
Recursion uses the call stack implicitly. These can also be written iteratively with an explicit stack — useful when recursion depth is a concern.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.value)
# push right first so left is processed first (LIFO)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return resultNotice the push order is reversed — right before left. Since a stack is LIFO, the last thing pushed comes out first. Pushing right first ensures left gets popped and processed first, matching the recursive order.
When to use which traversal
| Goal | Traversal |
|---|---|
| Get sorted values from a BST | Inorder |
| Copy or serialize a tree | Preorder |
| Delete a tree safely | Postorder |
| Evaluate an expression tree | Postorder |
| Print level by level | Level-order (BFS) |
| Find shortest path / closest node | Level-order (BFS) |
Complexity
| Traversal | Time | Space |
|---|---|---|
| Preorder | O(n) | O(h) recursive, O(n) iterative |
| Inorder | O(n) | O(h) recursive, O(n) iterative |
| Postorder | O(n) | O(h) recursive, O(n) iterative |
| Level-order | O(n) | O(w) — w is max width of tree |
Where h is tree height and w is the maximum number of nodes at any single level.