Tree, Graph and Dynamic Programming Questions
40 min · Advanced
Need help? Ask a tutor on WhatsApp (opens in a new tab)Trees, graphs and dynamic programming are where interviews get harder, but the questions are predictable. This lesson shows the fixed way to talk through each one. The full teaching is in the Binary Trees, Graphs and Dynamic Programming modules; here you practise the interview version.
Tree questions: solve the children, then combine
Tree recursion solves a question for a node by asking the same question of its left and right children and combining the answers. The base case is an empty node, None.
A tree node has a left and a right child, and each child is a smaller tree. Solve the same question for both children, then combine the two answers. Always write the empty-node case first. Revise: Height, diameter and balance (opens in a new tab)
def max_depth(node): if node is None: return 0 left = max_depth(node.left) right = max_depth(node.right) return 1 + max(left, right)Example 1 · A small tree: traversals, height and diameter
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
def inorder(node): return inorder(node.left) + [node.val] + inorder(node.right) if node else []
def height(node): return 0 if node is None else 1 + max(height(node.left), height(node.right))
def diameter(root): best = 0
def depth(node): nonlocal best if node is None: return 0 left, right = depth(node.left), depth(node.right) best = max(best, left + right) return 1 + max(left, right)
depth(root) return best
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))print(inorder(root))print(height(root))print(diameter(root))[4, 2, 5, 1, 3, 6] 3 4
What this code does
- Height counts nodes on the longest downward path. The diameter counts edges on the longest path between any two nodes: 4, 2, 1, 3, 6 is four edges.
- Diameter reuses the depth computation and updates one best value on the way, so it stays O(n) instead of recomputing heights at every node.
Example 2 · Level order traversal with a deque
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
from collections import deque
def level_order(root): levels = [] queue = deque([root] if root else []) while queue: level = [] for _ in range(len(queue)): node = queue.popleft() level.append(node.val) for child in (node.left, node.right): if child: queue.append(child) levels.append(level) return levels
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))print(level_order(root))[[1], [2, 3], [4, 5, 6]]
What this code does
- Taking
len(queue)at the start of the loop separates one level from the next. The empty tree returns an empty list. - Time is O(n). The space is the widest level, up to O(n).
Say: "Each node is visited once, so the time is O(n). The stack goes as deep as the tree is high, so the space is O(h): about log n if balanced and n if it is a chain."
Graph questions: BFS, DFS and a visited set
A visited set records the nodes a graph search has already reached. It stops loops on cycles and keeps breadth-first and depth-first search at O(V + E), where V is nodes and E is edges.
A graph is a set of nodes joined by edges, stored as a dict of lists. Because graphs can have cycles, remember every node you have already seen, or the search never ends. Revise: BFS and shortest path by edges (opens in a new tab)
from collections import deque
def distance(graph, start, goal): seen = {start} queue = deque([(start, 0)]) while queue: node, steps = queue.popleft() if node == goal: return steps for neighbour in graph[node]: if neighbour not in seen: seen.add(neighbour) queue.append((neighbour, steps + 1)) return -1Example 3 · Number of islands: depth-first search on a grid
def count_islands(grid): rows, cols = len(grid), len(grid[0]) seen = set() islands = 0 for r in range(rows): for c in range(cols): if grid[r][c] == "1" and (r, c) not in seen: islands += 1 stack = [(r, c)] seen.add((r, c)) while stack: x, y = stack.pop() for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1" and (nx, ny) not in seen: seen.add((nx, ny)) stack.append((nx, ny)) return islands
print(count_islands(["11000", "11000", "00100", "00011"]))3
What this code does
- Each unseen land cell starts a new island, and the stack spreads over its connected land. A cell is marked when it is pushed, so it is never pushed twice.
- An explicit stack avoids Python's recursion limit on a large grid. Time and space are O(rows times cols).
Example 4 · Course order with topological sort
from collections import deque
def course_order(count, rules): after = {i: [] for i in range(count)} waiting = [0] * count for first, then in rules: after[first].append(then) waiting[then] += 1 queue = deque(i for i in range(count) if waiting[i] == 0) order = [] while queue: course = queue.popleft() order.append(course) for nxt in after[course]: waiting[nxt] -= 1 if waiting[nxt] == 0: queue.append(nxt) return order if len(order) == count else []
print(course_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))print(course_order(2, [(0, 1), (1, 0)]))[0, 1, 2, 3] []
What this code does
- A course can be taken when it has no waiting prerequisites. Taking one lowers the count of each course that follows it.
- If a cycle exists, some courses never reach zero, so the order is too short and we return an empty list. Time is O(V + E).
Say: "BFS visits nearest nodes first, so the first time I reach the goal is the fewest edges. Mark nodes as seen when I add them to the queue, not when I take them out."
Dynamic programming: state, base case, transition
Dynamic programming solves a problem by storing the answers to smaller overlapping subproblems so each is computed once. It needs a state, a base case and a transition from smaller states.
Use dynamic programming when a problem repeats the same smaller questions and the answer is a best value or a count. Say what the state means, what the base case is, and how a state uses smaller ones. Revise: From recursion to memoization to a table (opens in a new tab)
from functools import lru_cache
@lru_cache(maxsize=None)def ways(steps): if steps <= 1: return 1 return ways(steps - 1) + ways(steps - 2)
print(ways(30))Example 5 · Coin change: recursion, memo and table
from functools import lru_cache
coins = (1, 5, 6, 9)
def brute(amount): # Exponential: the same amounts are solved again and again. if amount == 0: return 0 options = [brute(amount - c) for c in coins if c <= amount] return 1 + min(options) if options else float("inf")
@lru_cache(maxsize=None)def memo(amount): if amount == 0: return 0 options = [memo(amount - c) for c in coins if c <= amount] return 1 + min(options) if options else float("inf")
def table(amount): dp = [0] + [float("inf")] * amount for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount]
print(brute(11), memo(11), table(11))2 2 2
What this code does
- All three give 2 (5 plus 6). The greedy idea 'take the biggest coin' would give 9, 1, 1 which is three coins, so a greedy answer is wrong here.
- The table has amount + 1 cells and tries each coin: O(amount times coins) time, O(amount) space. Cells for impossible amounts stay at infinity.
Example 6 · Longest increasing subsequence with bisect
from bisect import bisect_left
def lis_length(nums): tails = [] # tails[i] = smallest tail of an increasing run of length i + 1 for value in nums: pos = bisect_left(tails, value) if pos == len(tails): tails.append(value) else: tails[pos] = value return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))4
What this code does
- The simple table is O(n squared). Keeping the smallest possible tail for each length lets
bisect_leftplace each value in O(log n). tailsis not itself the subsequence, only its length matters here. The total is O(n log n) time and O(n) space.
Without the cache this makes about 2 to the power n calls. With it each state is computed once, so the time is O(n).
The DP answer interviewers want to hear
A state is the small set of values that fully describes one subproblem, such as 'the best for amount a'. A transition is the rule that builds a state from smaller states, such as dp[a] = 1 + min(dp[a - coin]).
Walk through four sentences in order and you will rarely get lost. After that, mention how to save space when only the last few states are needed.
- State: say what dp[i] means in words.
- Base case: say the value for the smallest input, and what an impossible state holds.
- Transition: say how dp[i] uses earlier values, and the order to fill them.
- Answer and cost: say which cell is the answer, then time and space.
Next step
Check your understanding
12 quick questions