Week 02 - Binary Trees & Graphs

Reference extracted from the detailed guide.

Day 1-3: Binary Trees

Watch First (CRITICAL):

• NeetCode: Binary Tree playlist → https://www.youtube.com/watch?v=OnSn2XEQ4MY
• Abdul Bari: Tree Traversals → https://www.youtube.com/watch?v=BHB0B1jFKQc

Problems in Order:

Key Templates:

# Template: DFS Recursive
def dfs(node):
    if not node:
        return base_case
    left = dfs(node.left)
    right = dfs(node.right)
    return combine(left, right, node.val)

# Template: BFS Level Order
from collections import deque
def bfs(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    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

# Template: Validate BST
def isValidBST(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return (isValidBST(root.left, min_val, root.val) and 
            isValidBST(root.right, root.val, max_val))

Day 4-6: Graphs BFS/DFS

Watch First (CRITICAL):

• NeetCode: Graph playlist → https://www.youtube.com/watch?v=EgI5nU9etnU
• William Fiset: Graph Theory playlist → https://www.youtube.com/watch?v=DgXR2OWQnLc&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P

Problems in Order:

Key Templates:

# Template: DFS on Grid
def numIslands(grid):
    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):
            return
        if grid[i][j] != '1':
            return
        grid[i][j] = '#'  # mark visited
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

# Template: Topological Sort (DFS)
def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for crs, pre in prerequisites:
        graph[crs].append(pre)
    
    UNVISITED, VISITING, VISITED = 0, 1, 2
    states = [UNVISITED] * numCourses
    
    def dfs(crs):
        if states[crs] == VISITING:
            return False  # cycle detected
        if states[crs] == VISITED:
            return True
        
        states[crs] = VISITING
        for pre in graph[crs]:
            if not dfs(pre):
                return False
        states[crs] = VISITED
        return True
    
    return all(dfs(crs) for crs in range(numCourses))

# Template: BFS on Grid
from collections import deque
def bfs_grid(grid, start_i, start_j):
    queue = deque([(start_i, start_j, 0)])  # (row, col, distance)
    visited = {(start_i, start_j)}
    directions = [(0,1), (0,-1), (1,0), (-1,0)]
    
    while queue:
        i, j, dist = queue.popleft()
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]):
                if (ni, nj) not in visited and grid[ni][nj] != '#':
                    visited.add((ni, nj))
                    queue.append((ni, nj, dist + 1))

Day 7: Review + LeetCode Weekly Contest

• Sign up: https://leetcode.com/contest/
• Contests are Saturday 7:30 PM PST or Sunday 2:30 AM PST
• Do virtual contests if you miss live ones

---