Depth-First Search
DFS traversal: preorder, inorder, and postorder traversals. Understand recursive and iterative implementations.
Depth-First Search (DFS) on trees explores as deep as possible before backtracking. There are three main traversal orders: preorder, inorder, and postorder. Each visits nodes in a different sequence, suited for different problems.
The Three DFS Traversals
All three visit every node exactly once, but in different orders:
1
/ \
2 3
/ \
4 5
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)
Preorder Traversal (Node → Left → Right)
Visit the current node before its children.
def preorder(root):
if root is None:
return
print(root.val) # Process node
preorder(root.left) # Visit left subtree
preorder(root.right) # Visit right subtree
Collecting into a list:
def preorder_collect(root):
result = []
def traverse(node):
if node is None:
return
result.append(node.val)
traverse(node.left)
traverse(node.right)
traverse(root)
return result
Use cases:
- Copy a tree
- Serialize a tree
- Prefix expression (Polish notation)
- Build a tree from description
Inorder Traversal (Left → Node → Right)
Visit left subtree, then current node, then right subtree.
def inorder(root):
if root is None:
return
inorder(root.left) # Visit left subtree
print(root.val) # Process node
inorder(root.right) # Visit right subtree
Collecting into a list:
def inorder_collect(root):
result = []
def traverse(node):
if node is None:
return
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
BST Property
Inorder traversal of a Binary Search Tree produces values in sorted order. This is a key property for validating BSTs and finding k-th smallest elements.
Use cases:
- Get sorted values from BST
- Validate BST
- Expression evaluation (infix notation)
Postorder Traversal (Left → Right → Node)
Visit both subtrees before the current node.
def postorder(root):
if root is None:
return
postorder(root.left) # Visit left subtree
postorder(root.right) # Visit right subtree
print(root.val) # Process node
Collecting into a list:
def postorder_collect(root):
result = []
def traverse(node):
if node is None:
return
traverse(node.left)
traverse(node.right)
result.append(node.val)
traverse(root)
return result
Use cases:
- Delete a tree (delete children before parent)
- Calculate tree size or height
- Evaluate expression trees
- Postfix expression (Reverse Polish notation)
Visualizing Traversals
A
/ \
B C
/ \ \
D E F
Preorder: A B D E C F
- Visit A, then go left to B
- Visit B, go left to D
- Visit D (leaf), backtrack
- Visit E (leaf), backtrack to A
- Go right to C, visit C
- Go right to F, visit F
Inorder: D B E A C F
- Go left until leaf D
- Visit D, backtrack
- Visit B, go right to E
- Visit E, backtrack to A
- Visit A, go right to C
- Visit C, go right to F
- Visit F
Postorder: D E B F C A
- Go deep left to D
- Visit D, backtrack
- Visit E, backtrack to B
- Visit B, backtrack to A
- Go right to C, go right to F
- Visit F, backtrack
- Visit C, backtrack
- Visit A (last)
Iterative Implementations
Preorder with Stack
def preorder_iterative(root):
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
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
Inorder with Stack
def inorder_iterative(root):
result = []
stack = []
current = root
while current or stack:
# Go left as far as possible
while current:
stack.append(current)
current = current.left
# Process node
current = stack.pop()
result.append(current.val)
# Move to right subtree
current = current.right
return result
Postorder with Stack
def postorder_iterative(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1] # Reverse for postorder
Or using two stacks:
def postorder_two_stacks(root):
if root is None:
return []
result = []
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
result.append(stack2.pop().val)
return result
Morris Traversal (O(1) Space)
Inorder traversal without recursion or stack:
def inorder_morris(root):
result = []
current = root
while current:
if current.left is None:
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
# Make current the right child of predecessor
predecessor.right = current
current = current.left
else:
# Revert the change
predecessor.right = None
result.append(current.val)
current = current.right
return result
Morris Traversal Modifies Tree
Morris traversal temporarily modifies tree structure, then restores it. Don't use in multi-threaded environments or when tree structure must not change.
Common DFS Problems
Calculate Height
def height(root):
if root is None:
return -1 # or 0 depending on definition
return 1 + max(height(root.left), height(root.right))
Maximum Path Sum
def max_path_sum(root):
max_sum = float('-inf')
def dfs(node):
nonlocal max_sum
if node is None:
return 0
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
# Path through this node
max_sum = max(max_sum, left + right + node.val)
# Return max single path
return max(left, right) + node.val
dfs(root)
return max_sum
Diameter of Tree
def diameter(root):
max_diameter = 0
def dfs(node):
nonlocal max_diameter
if node is None:
return 0
left = dfs(node.left)
right = dfs(node.right)
max_diameter = max(max_diameter, left + right)
return 1 + max(left, right)
dfs(root)
return max_diameter
Summary Table
| Traversal | Order | Stack Behavior | Use Cases | |-----------|-------|----------------|-----------| | Preorder | Node, L, R | Pop, push R, push L | Copy, serialize | | Inorder | L, Node, R | Go left, pop, go right | Sorted BST values | | Postorder | L, R, Node | Reverse of modified preorder | Delete tree, eval expr |
Key Takeaways
- DFS explores depth before breadth
- Preorder: node first, then children (top-down)
- Inorder: left, node, right (sorted order for BST)
- Postorder: children first, then node (bottom-up)
- All can be implemented recursively or iteratively
- Morris traversal achieves O(1) space but modifies tree
- Choose traversal based on problem requirements
Understanding tree DFS is essential for most tree problems. The traversal order determines when you process each node relative to its children—a crucial detail for problems like path sums, tree construction, and expression evaluation.