Trees and Graphs Problem Set

Trees and graphs are both “follow the edges” problems — the difference is just how strict the shape is. This set starts with plain recursive tree traversals, moves into grid-as-graph problems, and finishes with two classic BFS-on-an-implicit-graph problems: Course Schedule and Word Ladder.

What you’ll learn

The recursive DFS on a tree template: handle the base case (None), then combine the answers from node.left and node.right.
BFS level order using a queue, one level at a time.
Treating a 2D grid as an implicit graph for flood-fill counting (Number of Islands).
Detecting a cycle in a directed graph (Course Schedule) and running BFS over an implicit word graph (Word Ladder).

How to use this set

Same loop as the other problem sets: read the problem, open the stub, find the # TODO, press Run, and match the printed output to the # expect comments. Each stub includes small helper functions (build_tree, build_graph, and similar) so the block runs standalone — you only need to fill in the one function under test. A collapsed Show solution follows each problem with a complete, annotated answer and its complexity.

Problems

1. Maximum Depth of Binary Tree — LC 104 — Easy

Open LC 104 on LeetCode

Pattern: DFS (post-order combine) — see Depth First Search.

Problem. Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to the farthest leaf.

max_depth.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def max_depth(root):
    # TODO: return the number of nodes on the longest root-to-leaf path
    pass
 
 
# Sample tests (press Run):
print(max_depth(build_tree([3, 9, 20, None, None, 15, 7])))   # expect 3
print(max_depth(build_tree([])))                                # expect 0

Show solution

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
 
 
print(max_depth(build_tree([3, 9, 20, None, None, 15, 7])))   # 3
print(max_depth(build_tree([])))                                # 0

A None node has depth 0; every other node’s depth is 1 plus the deeper of its two children’s depths. Time: $O(n)$ — every node is visited once. Space: $O(h)$ for the recursion stack, where h is the tree’s height.

2. Invert Binary Tree — LC 226 — Easy

Open LC 226 on LeetCode

Pattern: DFS (post-order swap) — see Depth First Search.

Problem. Given the root of a binary tree, invert it (mirror every subtree, left becomes right) and return the new root.

invert_tree.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def to_level_list(root):
    if root is None:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            result.append(None)
            continue
        result.append(node.val)
        queue.append(node.left)
        queue.append(node.right)
    while result and result[-1] is None:
        result.pop()
    return result
 
 
def invert_tree(root):
    # TODO: swap every node's left and right children, return the new root
    pass
 
 
# Sample tests (press Run):
print(to_level_list(invert_tree(build_tree([4, 2, 7, 1, 3, 6, 9]))))
# expect [4, 7, 2, 9, 6, 3, 1]

Show solution

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def to_level_list(root):
    if root is None:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            result.append(None)
            continue
        result.append(node.val)
        queue.append(node.left)
        queue.append(node.right)
    while result and result[-1] is None:
        result.pop()
    return result
 
 
def invert_tree(root):
    if root is None:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root
 
 
print(to_level_list(invert_tree(build_tree([4, 2, 7, 1, 3, 6, 9]))))
# [4, 7, 2, 9, 6, 3, 1]

Invert both children first, then swap them onto the current node — the order doesn’t actually matter here since the two subtrees don’t interact, but swapping after recursing keeps the logic easy to read. Time: $O(n)$ . Space: $O(h)$ for the recursion stack.

3. Validate Binary Search Tree — LC 98 — Medium

Open LC 98 on LeetCode

Pattern: DFS with propagated bounds — see Depth First Search.

Problem. Given the root of a binary tree, determine if it is a valid binary search tree: every node’s value must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree.

validate_bst.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def is_valid_bst(root):
    # TODO: return True only if every node's value fits its BST bounds
    pass
 
 
# Sample tests (press Run):
print(is_valid_bst(build_tree([2, 1, 3])))                       # expect True
print(is_valid_bst(build_tree([5, 1, 4, None, None, 3, 6])))      # expect False

Show solution

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def is_valid_bst(root):
    def validate(node, low, high):
        if node is None:
            return True
        if not (low < node.val < high):
            return False
        return validate(node.left, low, node.val) and validate(node.right, node.val, high)
 
    return validate(root, float("-inf"), float("inf"))
 
 
print(is_valid_bst(build_tree([2, 1, 3])))                       # True
print(is_valid_bst(build_tree([5, 1, 4, None, None, 3, 6])))      # False

Checking node.left.val < node.val and node.right.val > node.val at every node isn’t enough — a node deep in the left subtree still has to be less than every ancestor above it, not just its immediate parent. Carrying a (low, high) bound down through the recursion enforces that. Time: $O(n)$ . Space: $O(h)$ .

4. Binary Tree Level Order Traversal — LC 102 — Medium

Open LC 102 on LeetCode

Pattern: BFS, one level at a time — see Breadth First Search.

Problem. Given the root of a binary tree, return the level order traversal of its node values as a list of lists — one inner list per level, left to right.

level_order.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def level_order(root):
    # TODO: return a list of lists, one inner list per level, left to right
    pass
 
 
# Sample tests (press Run):
print(level_order(build_tree([3, 9, 20, None, None, 15, 7])))
# expect [[3], [9, 20], [15, 7]]

Show solution

python

from collections import deque
 
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root
 
 
def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):        # exactly the nodes at this level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result
 
 
print(level_order(build_tree([3, 9, 20, None, None, 15, 7])))
# [[3], [9, 20], [15, 7]]

Snapshot len(queue) before the inner loop — that’s exactly how many nodes belong to the current level, even though the loop body keeps appending their children onto the same queue. Time: $O(n)$ . Space: $O(n)$ for the queue and the output.

5. Number of Islands — LC 200 — Medium

Open LC 200 on LeetCode

Pattern: DFS flood fill on a grid — see Depth First Search.

Problem. Given an m x n 2D binary grid where "1" is land and "0" is water, return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

num_islands.py

def num_islands(grid):
    # TODO: return the number of islands (connected groups of '1's)
    pass
 
 
# Sample tests (press Run):
grid1 = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]
print(num_islands(grid1))   # expect 1
 
grid2 = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
print(num_islands(grid2))   # expect 3

Show solution

python

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
 
    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"     # mark visited by "draining" it
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)
 
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                sink(r, c)     # flood-fill the whole island so it's not recounted
    return islands
 
 
grid1 = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]
print(num_islands(grid1))   # 1
 
grid2 = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
print(num_islands(grid2))   # 3

Every time you find an unvisited "1", that’s a brand new island — flood fill (DFS) turns every connected "1" into a "0" so it’s never counted twice. Time: $O(rows \times cols)$ . Space: $O(rows \times cols)$ worst case for the recursion stack.

6. Course Schedule — LC 207 — Medium

Open LC 207 on LeetCode

Pattern: Cycle detection via DFS — see Depth First Search.

Problem. There are num_courses courses labeled 0 to num_courses - 1. prerequisites[i] = [a, b] means you must take course b before course a. Return True if you can finish all courses (i.e. the prerequisite graph has no cycle).

course_schedule.py

def can_finish(num_courses, prerequisites):
    # TODO: return True if all courses can be finished (no cycle in the graph)
    pass
 
 
# Sample tests (press Run):
print(can_finish(2, [[1, 0]]))           # expect True
print(can_finish(2, [[1, 0], [0, 1]]))   # expect False

Show solution

python

def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)
 
    state = [0] * num_courses    # 0 = unvisited, 1 = visiting, 2 = done
 
    def has_cycle(node):
        if state[node] == 1:
            return True          # back edge into a node still being visited -> cycle
        if state[node] == 2:
            return False          # already fully explored, safe
        state[node] = 1
        for neighbor in graph[node]:
            if has_cycle(neighbor):
                return True
        state[node] = 2
        return False
 
    return not any(has_cycle(i) for i in range(num_courses))
 
 
print(can_finish(2, [[1, 0]]))           # True
print(can_finish(2, [[1, 0], [0, 1]]))   # False

Three-color DFS: a node marked “visiting” that you reach again before it’s marked “done” means there’s a cycle — and a cyclic prerequisite graph can never be fully completed. Time: $O(V + E)$ . Space: $O(V + E)$ .

7. Clone Graph — LC 133 — Medium

Open LC 133 on LeetCode

Pattern: DFS + Hash Map (visited-node memo) — see Depth First Search.

Problem. Given a reference node in a connected undirected graph (every Node has an int val and a list of neighbors), return a deep copy (clone) of the graph.

clone_graph.py

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
 
 
def build_graph(adj_list):
    """adj_list[i] = 1-indexed neighbor values of node i + 1."""
    nodes = {i + 1: Node(i + 1) for i in range(len(adj_list))}
    for i, neighbors in enumerate(adj_list):
        nodes[i + 1].neighbors = [nodes[n] for n in neighbors]
    return nodes[1] if nodes else None
 
 
def to_adj_list(node):
    if node is None:
        return []
    visited = {}
    seen_ids = {id(node)}
    queue = [node]
    while queue:
        current = queue.pop(0)
        visited[current.val] = sorted(n.val for n in current.neighbors)
        for neighbor in current.neighbors:
            if id(neighbor) not in seen_ids:
                seen_ids.add(id(neighbor))
                queue.append(neighbor)
    return [visited[v] for v in sorted(visited)]
 
 
def clone_graph(node):
    # TODO: return a deep copy of the graph reachable from node
    pass
 
 
# Sample tests (press Run):
graph = build_graph([[2, 4], [1, 3], [2, 4], [1, 3]])
cloned = clone_graph(graph)
print(to_adj_list(cloned))     # expect [[2, 4], [1, 3], [2, 4], [1, 3]]
print(cloned is not graph)     # expect True (a real copy, not the same object)

Show solution

python

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
 
 
def build_graph(adj_list):
    nodes = {i + 1: Node(i + 1) for i in range(len(adj_list))}
    for i, neighbors in enumerate(adj_list):
        nodes[i + 1].neighbors = [nodes[n] for n in neighbors]
    return nodes[1] if nodes else None
 
 
def to_adj_list(node):
    if node is None:
        return []
    visited = {}
    seen_ids = {id(node)}
    queue = [node]
    while queue:
        current = queue.pop(0)
        visited[current.val] = sorted(n.val for n in current.neighbors)
        for neighbor in current.neighbors:
            if id(neighbor) not in seen_ids:
                seen_ids.add(id(neighbor))
                queue.append(neighbor)
    return [visited[v] for v in sorted(visited)]
 
 
def clone_graph(node):
    if node is None:
        return None
    visited = {}    # original node -> its clone
 
    def dfs(n):
        if n in visited:
            return visited[n]
        copy = Node(n.val)
        visited[n] = copy
        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy
 
    return dfs(node)
 
 
graph = build_graph([[2, 4], [1, 3], [2, 4], [1, 3]])
cloned = clone_graph(graph)
print(to_adj_list(cloned))     # [[2, 4], [1, 3], [2, 4], [1, 3]]
print(cloned is not graph)     # True

The visited map does double duty: it prevents infinite recursion around cycles, and it makes sure two edges pointing at the same original node end up pointing at the same clone. Time: $O(V + E)$ . Space: $O(V)$ .

8. Word Ladder — LC 127 — Hard

Open LC 127 on LeetCode

Pattern: BFS shortest path over an implicit graph — see Breadth First Search.

Problem. Given begin_word, end_word, and a word_list, return the length of the shortest transformation sequence from begin_word to end_word, changing exactly one letter at a time, where every intermediate word must exist in word_list. Return 0 if no such sequence exists.

word_ladder.py

def ladder_length(begin_word, end_word, word_list):
    # TODO: return the length of the shortest transformation sequence, or 0
    pass
 
 
# Sample tests (press Run):
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
# expect 5
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))
# expect 0

Show solution

python

from collections import deque
import string
 
 
def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
 
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
 
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            for ch in string.ascii_lowercase:
                if ch == word[i]:
                    continue
                candidate = word[:i] + ch + word[i + 1:]
                if candidate in words and candidate not in visited:
                    visited.add(candidate)
                    queue.append((candidate, steps + 1))
    return 0
 
 
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
# 5
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))
# 0

Every word in word_list is a node; two words are connected if they differ by exactly one letter. BFS from begin_word finds the shortest transformation sequence because BFS explores level by level — the first time you reach end_word, you’ve found the fewest possible steps. Time: $O(n \cdot L^2 \cdot 26)$ for n words of length L (generating every one-letter variant of every word). Space: $O(n)$ .

Complexity

For trees, n is the node count and h the height — $O(\log n)$ balanced, $O(n)$ degenerate. For graphs, V and E.

#	Problem	Time	Space	Where the space goes
1	Maximum Depth	$O(n)$	$O(h)$ recursive, $O(n)$ iterative BFS	Call stack, or the widest level
2	Invert Binary Tree	$O(n)$	$O(h)$	Call stack
3	Validate BST	$O(n)$	$O(h)$	Call stack; the bounds are two extra locals
4	Level Order Traversal	$O(n)$	$O(w)$ — the widest level, up to $n/2$	The queue
5	Number of Islands	$O(mn)$	$O(mn)$ worst case	DFS stack on an all-land grid
6	Course Schedule	$O(V + E)$	$O(V + E)$	Adjacency list plus the in-degree array
7	Clone Graph	$O(V + E)$	$O(V)$	The old-to-new node map
8	Word Ladder	$O(N \cdot L^2 \cdot 26)$ naive, $O(N \cdot L \cdot 26)$ with wildcard buckets	$O(N \cdot L)$	`N` words of length `L`

Five things worth being precise about:

$O(h)$ is not $O(\log n)$ . Every recursive tree solution is $O(h)$ stack space, which is $O(\log n)$ only when balanced. A 10,000-node path is a legal input and it exceeds CPython’s ~1000-frame limit — so ” $O(h)$ , which is $O(n)$ in the worst case, and that is a real crash in Python” is the complete answer.
BFS space is the widest level, not the height. For a complete tree the last level holds about n/2 nodes, so level-order is $O(n)$ space where the recursive depth-first version is $O(\log n)$ . BFS trades space for the level structure it gives you.
Number of Islands is $O(mn)$ time regardless of approach — each cell is visited once. The approaches differ in space: recursive DFS is $O(mn)$ stack in the worst case, BFS is $O(\min(m,n))$ for the frontier, and union-find is $O(mn)$ for the parent array.
Word Ladder’s bound has three factors, and the improvement is in the middle one. Generating every one-letter variant of a word is $O(L \cdot 26)$ , and then a naive implementation compares each candidate against the dictionary at $O(L)$ per hash. Precomputing wildcard buckets (h*t -> [hot, hit, hat]) removes one L.
Clone Graph’s map is the algorithm, not an optimisation. Without it you recurse forever on any cycle. $O(V)$ space is mandatory.

Pitfalls

Validating a BST with only local parent-child comparisons. Checking left < node < right at each node is not enough — bounds must be inherited. The tree 10 / (5, 15 / (6, 20)) passes every local check and is not a BST: 6 sits in 10’s right subtree. Verified — the bounds version returns False, the local version returns True, and the in-order walk [5, 10, 6, 15, 20] confirms it is not sorted.
Using <= in the BST bounds. LeetCode 98 requires strictly increasing, so equal values are invalid. lo < node.val < hi, not <=.
Forgetting float('-inf') / float('inf') as the initial bounds, or using integer sentinels that a test value can reach. LC 98’s values span the full 32-bit range.
Level order without snapshotting len(queue). Take size = len(q) before the inner loop. Read len(q) inside it and you consume nodes the current iteration just appended, collapsing all levels into one.
Level order returning [[]] for an empty tree. The guard must return []. Verified: the correct version gives [] for None and [[1]] for a single node.
Number of Islands: marking visited after enqueueing. Mark the cell the moment you push it, not when you pop it — otherwise the same cell enters the queue several times from different neighbours, and a large grid degrades badly or exhausts memory.
Number of Islands: mutating the input grid to mark visited. Fast and $O(1)$ extra space, but it destroys the caller’s data. Fine if you say so; a surprise if you do not.
Course Schedule: building the edge direction backwards. [a, b] means “to take a you must first take b”, so the edge runs b -> a and a’s in-degree increases. Reverse it and you detect cycles correctly but answer a different question on acyclic input.
Course Schedule: checking whether the queue emptied rather than counting. The condition is processed == n. An empty queue with unprocessed nodes remaining is the cycle.
Clone Graph: no visited map. Any cycle recurses forever. And the map must be keyed on the original node, storing the clone — the standard slip is to check whether the clone exists by looking it up in the wrong direction.
Clone Graph: returning a shallow copy. Every neighbour list must contain clones, not originals. A test that only checks values passes; one that checks identity does not.
Word Ladder: not checking endWord is in the dictionary first. If it is absent the answer is 0, and the BFS would otherwise scan the entire word set to discover that.
Word Ladder: counting edges instead of nodes. The answer is the number of words in the sequence including both ends, so seed the queue with distance 1, not 0.
Recursion depth on any of these. A path-shaped tree or grid of 10,000 nodes is legal input and CPython dies at ~1000 frames. Say it, and offer the iterative form.

Drills

Three micro-drills on the exact lines that decide these problems.

Drill 1 — BST validation needs inherited bounds

Drill 2 — level order needs the size snapshot

Drill 3 — Kahn’s topological sort counts, it does not just drain

Interview follow-ups

They ask	On which problem	The answer
“Do it iteratively”	Maximum Depth, Invert, Validate BST	BFS with a queue for depth; an explicit stack for the others. The real reason is not elegance — it is that CPython dies at ~1000 frames and a path-shaped tree of 10,000 nodes is legal input
“What is the space complexity, exactly?”	any recursive tree solution	$O(h)$ , which is $O(\log n)$ balanced and $O(n)$ degenerate. Quoting $O(\log n)$ unconditionally assumes a balance the problem never promised
“Why is BFS more space than DFS here?”	Level Order	BFS holds the widest level, about `n/2` for a complete tree, so $O(n)$ ; recursive DFS holds one root-to-leaf path, $O(\log n)$ balanced. You pay space to get the level structure
“Validate a BST without the bounds”	Validate BST	In-order traversal must be strictly increasing — track only the previous value, $O(1)$ extra beyond the stack. Both are correct; the bounds version fails faster on a bad tree
“Why isn’t checking each node against its children enough?”	Validate BST	`10 / (5, 15 / (6, 20))` passes every local check and is not a BST — 6 is in 10’s right subtree. Violations can be between a node and its grandparent, which only an inherited bound sees
“Count islands without touching the input”	Number of Islands	A separate `visited` set at $O(mn)$ , or union-find over the land cells. Mutating the grid is $O(1)$ extra space and destroys the caller’s data — fine if you announce it
“Now count distinct island shapes”	Number of Islands	Normalise each island’s cell coordinates relative to its top-left cell and hash the resulting frozenset — LC 694. Same traversal, different accumulator
“Return the course order, not just feasibility”	Course Schedule	Collect nodes as you pop them — LC 210. Same algorithm; if `len(order) != n` there is a cycle, and you return `[]`
“DFS instead of Kahn’s?”	Course Schedule	Three-colour DFS: grey means on the current path, so a grey neighbour is a back edge and hence a cycle. Equivalent bound; Kahn’s also hands you the order for free
“Clone a graph with no cycles guaranteed”	Clone Graph	The map is still needed for shared nodes — a DAG with two paths to one node would clone it twice without it. Only a tree makes the map optional
“Speed up Word Ladder”	Word Ladder	Two-ended BFS from both `beginWord` and `endWord`, expanding whichever frontier is smaller — roughly a square-root reduction in explored nodes. And precompute wildcard buckets (`h*t`) so neighbour generation is $O(L \cdot 26)$ rather than a dictionary scan
“Return the actual ladder”	Word Ladder	LC 126 — record parents per level rather than a single visited set, then walk back. Substantially harder than counting, and the level-by-level structure is what makes it possible at all

Practice

Every problem on this page, generated from the problem database — so each row carries its sheet membership and reported companies, and the checkboxes remember what you have finished. The walkthroughs above are the teaching; this is the tracker.

8 problems

1 easy6 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

104Maximum Depth of Binary TreeeasyNeetCode 150Blind 75LeetCode Top Interview 150
200Number of IslandsmediumNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbytedance
102Binary Tree Level Order TraversalmediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbytedance
207Course SchedulemediumNeetCode 150Blind 75LeetCode Top Interview 150googleamazonmetabytedance
133Clone GraphmediumNeetCode 150Blind 75LeetCode Top Interview 150metagoogleamazon
98Validate Binary Search TreemediumNeetCode 150Blind 75LeetCode Top Interview 150
226Invert Binary TreemediumNeetCode 150Blind 75LeetCode Top Interview 150
127Word LadderhardNeetCode 150LeetCode Top Interview 150amazongooglebytedance

Self-check

pch.quizTag pch.quizDefaultTitle

Is the tree `10 / (5, 15 / (6, 20))` a valid BST, and what does a local parent-child check say?

pch.quizShowAnswer

B — Invalid -- but the local check wrongly says valid, because 6's violation is with its grandparent 10 — Verified: the bounds version returns False and the local version returns True. Every parent-child pair is individually fine -- 5 < 10, 15 > 10, 6 < 15, 20 > 15 -- yet 6 sits in 10's right subtree and must exceed 10. The in-order walk [5, 10, 6, 15, 20] is not sorted, which is the other way to see it.
In level-order traversal, why must `size = len(q)` be taken before the inner loop?

pch.quizShowAnswer

B — Reading len(q) inside the loop would include children appended during this same iteration, collapsing every level into one — The snapshot is what creates the level boundary. Without it the inner loop keeps consuming as the queue grows, so all nodes land in a single flat level -- the values are all present and the grouping is wrong, which is easy to miss if you only check membership. (len() on a deque is O(1); speed is not the issue.)
What should `level_order(None)` return?

pch.quizShowAnswer

B — [] -- an empty list of levels — No tree means no levels, so the outer list is empty. [[]] asserts there is one level that happens to be empty, which is a different claim and fails LC 102. The guard is `if not root: return []` before touching the queue -- and note [[1]] for a single node, so the wrapper is right in the non-empty case.
Course Schedule with n = 2 and prerequisites [[1,0],[0,1]]. What does Kahn's algorithm do?

pch.quizShowAnswer

B — Both nodes have in-degree 1, so the queue starts empty, the loop never runs, `done` stays 0, and `done == n` is False — This is exactly why the return is a count rather than a queue check. Every node in a cycle has a non-zero in-degree, so nothing seeds the queue at all. Returning True on an empty queue would report success on the cycle -- `done == n` is what distinguishes "finished" from "stuck".
`prerequisites[i] = [a, b]` means you must take b before a. Which edge do you build?

pch.quizShowAnswer

B — b -> a, and increment a's in-degree — Dependencies point from the prerequisite to the thing that depends on it: finishing b unlocks a. Reversing this still detects cycles correctly -- a cycle is a cycle in either direction -- so it passes the cycle tests and then produces a reversed order on LC 210, which is the version that catches it.
Why does Clone Graph need an old-to-new map even if you are told the graph is acyclic?

pch.quizShowAnswer

B — A DAG can have two paths to the same node, which would be cloned twice; only a tree makes the map optional — Cycles make the map necessary for *termination*; shared nodes make it necessary for *correctness*. Without it, a diamond-shaped DAG produces two distinct clones of the bottom node, so the copy has more nodes than the original. Only a tree -- exactly one path to every node -- lets you skip it.
Number of Islands: where should a cell be marked visited in the BFS version?

pch.quizShowAnswer

B — The moment it is pushed -- otherwise several neighbours enqueue the same cell before any of them pops it — Marking on pop still terminates and still counts correctly, but a cell can sit in the queue many times over, so the queue can grow far beyond the frontier -- on a large all-land grid that is a memory problem rather than a wrong answer. Mark on push and each cell enters exactly once.
The recursive solutions here are O(h) space. Why is that worth stating rather than saying O(log n)?

pch.quizShowAnswer

B — h is O(n) for a degenerate tree, and a 10,000-node path is legal input that exceeds CPython's ~1000-frame limit -- a real crash, not a theoretical one — O(log n) quietly assumes balance the problem never promised. A path-shaped tree makes h = n, and in CPython that is a RecursionError rather than a slow answer. The complete response names O(h), notes the degenerate case, and offers the iterative rewrite -- which is also what the "do it iteratively" follow-up is really after.

Recap

Binary tree problems almost always reduce to “handle None, then combine the results from node.left and node.right” — that’s DFS.
BFS processes a tree or graph one full level/layer at a time, which is exactly what you need for level order traversal and for the shortest-path guarantee in Word Ladder.
A 2D grid is just a graph in disguise: Number of Islands flood-fills connected land the same way DFS explores connected graph nodes.
Course Schedule and Clone Graph both lean on a small piece of state per node — a three-color visited array for cycle detection, a visited-to-clone map for deep copying.

You’ve now worked through all three problem sets — Getting Started, Arrays and Strings, and Trees and Graphs. From here, the fastest way to keep improving is repetition on the real LeetCode judge: re-solve a few of these from a blank file, without peeking at Show solution, until the pattern comes out automatically.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading