Skip to content
Python Central Hub

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 (NoneNone), then combine the answers from node.leftnode.left and node.rightnode.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# TODO, press Run, and match the printed output to the # expect# expect comments. Each stub includes small helper functions (build_treebuild_tree, build_graphbuild_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
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
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 NoneNone node has depth 0; every other node’s depth is 1 plus the deeper of its two children’s depths. Time: O(n)O(n) — every node is visited once. Space: O(h)O(h) for the recursion stack, where hh 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]
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]
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)O(n). Space: O(h)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
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
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.valnode.left.val < node.val and node.right.val > node.valnode.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)(low, high) bound down through the recursion enforces that. Time: O(n)O(n). Space: O(h)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]]
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]]
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)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)O(n). Space: O(n)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 nm x n 2D binary grid where "1""1" is land and "0""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
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
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""1", that’s a brand new island — flood fill (DFS) turns every connected "1""1" into a "0""0" so it’s never counted twice. Time: O(rows×cols)O(rows \times cols). Space: O(rows×cols)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_coursesnum_courses courses labeled 00 to num_courses - 1num_courses - 1. prerequisites[i] = [a, b]prerequisites[i] = [a, b] means you must take course bb before course aa. Return TrueTrue 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
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
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)O(V + E). Space: O(V+E)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 NodeNode has an int valint val and a list of neighborsneighbors), 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)
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
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 visitedvisited 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)O(V + E). Space: O(V)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_wordbegin_word, end_wordend_word, and a word_listword_list, return the length of the shortest transformation sequence from begin_wordbegin_word to end_wordend_word, changing exactly one letter at a time, where every intermediate word must exist in word_listword_list. Return 00 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
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
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_listword_list is a node; two words are connected if they differ by exactly one letter. BFS from begin_wordbegin_word finds the shortest transformation sequence because BFS explores level by level — the first time you reach end_wordend_word, you’ve found the fewest possible steps. Time: O(n⋅L2⋅26)O(n \cdot L^2 \cdot 26) for nn words of length LL (generating every one-letter variant of every word). Space: O(n)O(n).

Recap

  • Binary tree problems almost always reduce to “handle NoneNone, then combine the results from node.leftnode.left and node.rightnode.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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Was this page helpful?

Let us know how we did