Intermediate

Mock Exam 3: Trees & Graphs

Three Medium-level problems testing BFS, DFS, and topological sort. These are among the most common interview topics at top tech companies. Target time: 60 minutes total.

Problem 1: Binary Tree Level Order Traversal (Medium)

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Examples

Input: root = [3, 9, 20, null, null, 15, 7]
        3
       / \
      9   20
         /  \
        15   7
Output: [[3], [9, 20], [15, 7]]

Input: root = [1]
Output: [[1]]

Input: root = []
Output: []

Constraints

• Number of nodes: [0, 2000]
• -1000 ≤ Node.val ≤ 1000

Solution: BFS with Queue

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 level_order(root):
    """BFS level order traversal.

    Time: O(n) - visit every node once
    Space: O(n) - queue holds up to n/2 nodes (last level)

    Use a queue. For each level, process all nodes
    currently in the queue, then add their children.
    The key is using len(queue) to know how many
    nodes belong to the current level.
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            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

# DFS alternative (recursive):
def level_order_dfs(root):
    """DFS approach: track depth to assign levels.

    Time: O(n), Space: O(n)
    """
    result = []

    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):
            result.append([])
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return result

# Test
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(level_order(root))  # [[3], [9, 20], [15, 7]]

Problem 2: Number of Islands (Medium)

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

Examples

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints

• m == grid.length, n == grid[i].length
• 1 ≤ m, n ≤ 300
• grid[i][j] is '0' or '1'

Solution: DFS Flood Fill

def num_islands(grid):
    """DFS flood fill to count connected components.

    Time: O(m * n) - visit every cell once
    Space: O(m * n) - recursion stack in worst case

    Scan the grid. When we find a '1', increment
    the island count and use DFS to "sink" the
    entire island by marking all connected '1's as '0'.
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        # Boundary check and water check
        if (r < 0 or r >= rows or
            c < 0 or c >= cols or
            grid[r][c] == '0'):
            return

        grid[r][c] = '0'  # Mark as visited (sink)

        # Explore all 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

# BFS alternative:
def num_islands_bfs(grid):
    """BFS approach - avoids deep recursion stack.

    Time: O(m * n), Space: O(min(m, n)) for queue
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                grid[r][c] = '0'
                queue = deque([(r, c)])
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = cr + dr, cc + dc
                        if (0 <= nr < rows and 0 <= nc < cols
                                and grid[nr][nc] == '1'):
                            grid[nr][nc] = '0'
                            queue.append((nr, nc))

    return count

Problem 3: Course Schedule (Medium)

There are numCourses courses labeled 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return True if you can finish all courses, or False if there is a cycle.

Examples

Input: numCourses = 2, prerequisites = [[1, 0]]
Output: True
Explanation: Take course 0 first, then course 1.

Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False
Explanation: Circular dependency - impossible.

Constraints

• 1 ≤ numCourses ≤ 2000
• 0 ≤ prerequisites.length ≤ 5000
• prerequisites[i].length == 2
• All prerequisite pairs are unique

Solution: DFS Cycle Detection

from collections import defaultdict

def can_finish_dfs(numCourses, prerequisites):
    """DFS cycle detection in directed graph.

    Time: O(V + E) - visit each node and edge once
    Space: O(V + E) - adjacency list + recursion stack

    Build adjacency list. For each unvisited node,
    run DFS. Use 3 states:
    - 0: unvisited
    - 1: visiting (in current DFS path - cycle if revisited)
    - 2: visited (fully processed - safe)
    """
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # 0=unvisited, 1=visiting, 2=visited
    state = [0] * numCourses

    def has_cycle(node):
        if state[node] == 1:  # Back edge = cycle
            return True
        if state[node] == 2:  # Already processed
            return False

        state[node] = 1  # Mark as visiting

        for neighbor in graph[node]:
            if has_cycle(neighbor):
                return True

        state[node] = 2  # Mark as visited
        return False

    for course in range(numCourses):
        if has_cycle(course):
            return False

    return True

Solution: BFS Topological Sort (Kahn's Algorithm)

def can_finish(numCourses, prerequisites):
    """BFS topological sort (Kahn's algorithm).

    Time: O(V + E)
    Space: O(V + E)

    Count in-degrees. Start with nodes that have
    in-degree 0 (no prerequisites). Process them,
    decrement neighbors' in-degrees. If all nodes
    are processed, no cycle exists.
    """
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    # Start with courses that have no prerequisites
    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)

    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If all courses processed, no cycle
    return processed == numCourses

# Test
print(can_finish(2, [[1, 0]]))           # True
print(can_finish(2, [[1, 0], [0, 1]]))   # False

Score Your Performance

Result	Score	Next Step
All 3 solved optimally in < 60 min	⭐ Excellent	Move to Mock Exam 4
All 3 solved (any approach) in < 60 min	👍 Good	Review topological sort, then Mock Exam 4
2 solved in 60 min	🔄 Developing	Practice BFS/DFS on 5 more graph problems
1 or 0 solved	📚 Study More	Study graph traversal fundamentals, retry in 3 days