Tree and graph problems make up a large portion of coding interviews at top tech companies. The key is recognizing patterns. In this article, you will learn the five most common tree patterns and four most common graph patterns, with full code examples.
We show core examples in Kotlin, Python, and Go.
Tree Pattern 1: DFS Traversal Variants
Different traversals solve different problems:
- Inorder (left, root, right): BST gives sorted order
- Preorder (root, left, right): Serialize/copy a tree
- Postorder (left, right, root): Delete a tree, calculate subtree values
Inorder Traversal (Iterative)
Python:
def inorder_traversal(root):
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
Kth Smallest Element in BST
Use inorder traversal. The kth element visited is the answer.
Python:
def kth_smallest(root, k):
stack = []
current = root
count = 0
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
count += 1
if count == k:
return current.val
current = current.right
Kotlin:
fun kthSmallest(root: TreeNode?, k: Int): Int {
val stack = ArrayDeque<TreeNode>()
var current = root
var count = 0
while (current != null || stack.isNotEmpty()) {
while (current != null) {
stack.addLast(current)
current = current.left
}
current = stack.removeLast()
count++
if (count == k) return current.`val`
current = current.right
}
return -1
}
Tree Pattern 2: BFS Level-Order Processing
Process tree level by level using a queue. Track levels explicitly.
Binary Tree Right Side View
Return the rightmost node at each level.
Python:
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Zigzag Level Order Traversal
Alternate between left-to-right and right-to-left at each level.
Python:
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
level.reverse()
result.append(level)
left_to_right = not left_to_right
return result
Go:
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
result := [][]int{}
queue := []*TreeNode{root}
leftToRight := true
for len(queue) > 0 {
size := len(queue)
level := make([]int, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
idx := i
if !leftToRight {
idx = size - 1 - i
}
level[idx] = node.Val
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
leftToRight = !leftToRight
}
return result
}
Tree Pattern 3: Path Problems
Calculate paths, sums, and distances in trees using DFS.
Diameter of Binary Tree
The diameter is the longest path between any two nodes (number of edges).
Python:
def diameter_of_binary_tree(root):
diameter = 0
def height(node):
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter
Kotlin:
fun diameterOfBinaryTree(root: TreeNode?): Int {
var diameter = 0
fun height(node: TreeNode?): Int {
if (node == null) return 0
val left = height(node.left)
val right = height(node.right)
diameter = maxOf(diameter, left + right)
return 1 + maxOf(left, right)
}
height(root)
return diameter
}
Path Sum III
Count paths that sum to a target value. Paths do not need to start at the root.
Python:
def path_sum(root, target_sum):
prefix_sums = {0: 1}
count = 0
def dfs(node, current_sum):
nonlocal count
if not node:
return
current_sum += node.val
count += prefix_sums.get(current_sum - target_sum, 0)
prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
dfs(node.left, current_sum)
dfs(node.right, current_sum)
prefix_sums[current_sum] -= 1 # Backtrack
dfs(root, 0)
return count
This uses the prefix sum technique on tree paths. Time: O(n). Space: O(n).
Tree Pattern 4: Subtree Problems
Compare subtrees, check symmetry, or validate structure.
Same Tree
Python:
def is_same_tree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.val == q.val and
is_same_tree(p.left, q.left) and
is_same_tree(p.right, q.right))
Symmetric Tree
Python:
def is_symmetric(root):
def mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
mirror(left.left, right.right) and
mirror(left.right, right.left))
return mirror(root.left, root.right) if root else True
Tree Pattern 5: BST Properties
Validate BST
Python:
def is_valid_bst(root, low=float("-inf"), high=float("inf")):
if not root:
return True
if root.val <= low or root.val >= high:
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
Lowest Common Ancestor in BST
In a BST, if both values are smaller than current node, go left. If both are larger, go right. Otherwise, the current node is the LCA.
Python:
def lowest_common_ancestor_bst(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
Go:
func lowestCommonAncestorBST(root, p, q *TreeNode) *TreeNode {
for root != nil {
if p.Val < root.Val && q.Val < root.Val {
root = root.Left
} else if p.Val > root.Val && q.Val > root.Val {
root = root.Right
} else {
return root
}
}
return nil
}
Lowest Common Ancestor in Binary Tree (not BST)
Python:
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left or right
Time: O(n). Space: O(n) for recursion stack.
Graph Pattern 1: BFS Shortest Path
Use BFS for shortest path in unweighted graphs and grids.
Walls and Gates
Fill each empty room with the distance to the nearest gate. Multi-source BFS from all gates.
Python:
from collections import deque
def walls_and_gates(rooms):
if not rooms:
return
rows, cols = len(rooms), len(rooms[0])
queue = deque()
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
while queue:
r, c = queue.popleft()
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
Graph Pattern 2: DFS Connected Components
Count or label connected components using DFS.
Number of Provinces
Given an adjacency matrix, find the number of connected components.
Python:
def find_circle_num(is_connected):
n = len(is_connected)
visited = [False] * n
provinces = 0
def dfs(city):
visited[city] = True
for neighbor in range(n):
if is_connected[city][neighbor] == 1 and not visited[neighbor]:
dfs(neighbor)
for city in range(n):
if not visited[city]:
provinces += 1
dfs(city)
return provinces
Graph Pattern 3: Topological Sort
Order vertices in a directed acyclic graph (DAG) such that for every edge u -> v, u comes before v.
Course Schedule II
Python:
from collections import deque
def find_order(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == num_courses else []
Kotlin:
fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
val graph = Array(numCourses) { mutableListOf<Int>() }
val inDegree = IntArray(numCourses)
for ((course, prereq) in prerequisites) {
graph[prereq].add(course)
inDegree[course]++
}
val queue = ArrayDeque<Int>()
for (i in 0 until numCourses) {
if (inDegree[i] == 0) queue.add(i)
}
val order = mutableListOf<Int>()
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
order.add(node)
for (neighbor in graph[node]) {
inDegree[neighbor]--
if (inDegree[neighbor] == 0) queue.add(neighbor)
}
}
return if (order.size == numCourses) order.toIntArray() else intArrayOf()
}
Graph Pattern 4: Union-Find for Dynamic Connectivity
Use Union-Find when components merge over time.
Redundant Connection
Find the edge that, when removed, makes the graph a tree (no cycles).
Python:
def find_redundant_connection(edges):
parent = list(range(len(edges) + 1))
rank = [0] * (len(edges) + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # Cycle detected
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
Decision Guide: Which Pattern to Use
| Problem Type | Pattern |
|---|---|
| Get sorted elements from BST | Inorder DFS |
| Level-by-level processing | BFS with level tracking |
| Shortest path in tree/graph | BFS |
| Path sum, diameter, depth | DFS with return value |
| Compare two trees | Recursive DFS |
| BST search, validate, LCA | BST property + DFS |
| Course ordering, build order | Topological sort (BFS Kahn’s) |
| Connected components | DFS or Union-Find |
| Dynamic connectivity | Union-Find |
Common Mistakes
Using DFS for shortest path. DFS does not guarantee shortest path. Use BFS for unweighted shortest path.
Not handling null nodes. Always check for null/None before accessing children.
Forgetting to pass updated bounds in validate BST. Each recursive call must narrow the valid range.
Not backtracking in path sum problems. When using hash maps for prefix sums on trees, undo the addition after processing both subtrees.
Practice Problems
| Problem | Pattern | LeetCode # |
|---|---|---|
| Binary Tree Right Side View | BFS level-order | #199 |
| Kth Smallest Element in BST | Inorder DFS | #230 |
| Diameter of Binary Tree | DFS path | #543 |
| Lowest Common Ancestor | DFS recursive | #236 |
| Validate BST | DFS with bounds | #98 |
| Course Schedule II | Topological sort | #210 |
| Number of Provinces | DFS connected components | #547 |
| Redundant Connection | Union-Find | #684 |
What’s Next?
Tree and graph patterns are essential for interviews. The next article goes deep on Dynamic Programming Patterns — knapsack, string DP, grid DP, and state machine patterns that appear in the hardest interview questions.
Next: DSA Tutorial #22: Dynamic Programming Patterns
Full series: DSA from Zero to Interview Ready