Part 4: Advanced Data Structures

The Turning Point in My Interview Prep

After mastering arrays and linked lists, I hit a wall with tree and graph problems. They seemed impossibly complex. The breakthrough came when I realized: trees and graphs are just linked lists with multiple pointers. This mental model transformed my approach.

Binary Trees

Understanding Trees Visually

I always draw trees before coding:

       1
      / \
     2   3
    / \
   4   5

Tree Node Definition

class TreeNode:
    """Binary tree node"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Helper function I use constantly
def create_tree(values: list) -> TreeNode:
    """Create binary tree from level-order array"""
    if not values:
        return None
    
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    
    while queue and i < len(values):
        node = queue.pop(0)
        
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    
    return root

Core Tree Traversal Patterns

Pattern 1: Depth-First Search (DFS)

Inorder Traversal (Left, Root, Right)

def inorder_traversal(root: TreeNode) -> list[int]:
    """
    Inorder: Left -> Root -> Right
    For BST, this gives sorted order!
    
    Time: O(n), Space: O(h) where h is height
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        
        dfs(node.left)           # Left
        result.append(node.val)  # Root
        dfs(node.right)          # Right
    
    dfs(root)
    return result

# Iterative approach (what I use in interviews)
def inorder_iterative(root: TreeNode) -> list[int]:
    """Iterative inorder using stack"""
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go left as far as possible
        while current:
            stack.append(current)
            current = current.left
        
        # Process node
        current = stack.pop()
        result.append(current.val)
        
        # Go right
        current = current.right
    
    return result

# Test
root = create_tree([1, None, 2, 3])
print(inorder_traversal(root))  # [1, 3, 2]

Preorder and Postorder

def preorder_traversal(root: TreeNode) -> list[int]:
    """
    Preorder: Root -> Left -> Right
    Useful for: Creating copy of tree
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # Root
        dfs(node.left)           # Left
        dfs(node.right)          # Right
    
    dfs(root)
    return result

def postorder_traversal(root: TreeNode) -> list[int]:
    """
    Postorder: Left -> Right -> Root
    Useful for: Deleting tree, calculating height
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # Left
        dfs(node.right)          # Right
        result.append(node.val)  # Root
    
    dfs(root)
    return result

Pattern 2: Breadth-First Search (BFS)

Level Order Traversal

def level_order(root: TreeNode) -> list[list[int]]:
    """
    BFS - process nodes level by level
    
    My approach: Queue to track nodes at each level
    Time: O(n), Space: O(w) where w is max width
    """
    if not root:
        return []
    
    from collections import deque
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        # Process all nodes at current level
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            # Add children for next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

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

Common Tree Problems

Problem: Maximum Depth of Binary Tree

def max_depth(root: TreeNode) -> int:
    """
    Find maximum depth of tree
    
    My approach: Recursive DFS
    Base case: None -> 0
    Recursive: 1 + max(left_depth, right_depth)
    
    Time: O(n), Space: O(h)
    """
    if not root:
        return 0
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return 1 + max(left_depth, right_depth)

# Iterative BFS approach
def max_depth_bfs(root: TreeNode) -> int:
    """BFS approach - count levels"""
    if not root:
        return 0
    
    from collections import deque
    queue = deque([root])
    depth = 0
    
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return depth

Problem: Validate Binary Search Tree

This problem taught me to think about constraints:

def is_valid_bst(root: TreeNode) -> bool:
    """
    Validate if tree is valid BST
    
    My insight: Not just left < root < right
                Must satisfy: left subtree < root < right subtree
    
    Approach: Track valid range for each node
    Time: O(n), Space: O(h)
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        # Check if node value is in valid range
        if not (min_val < node.val < max_val):
            return False
        
        # Validate subtrees with updated ranges
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

# Alternative: Inorder traversal should be sorted
def is_valid_bst_inorder(root: TreeNode) -> bool:
    """Using inorder traversal property"""
    self.prev = float('-inf')
    
    def inorder(node):
        if not node:
            return True
        
        # Check left subtree
        if not inorder(node.left):
            return False
        
        # Check current node
        if node.val <= self.prev:
            return False
        self.prev = node.val
        
        # Check right subtree
        return inorder(node.right)
    
    return inorder(root)

Problem: Lowest Common Ancestor

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Find LCA of two nodes in BST
    
    My approach: Use BST property
    - If both < root, LCA is in left
    - If both > root, LCA is in right
    - Otherwise, root is LCA
    
    Time: O(h), Space: O(1)
    """
    while root:
        # Both nodes in left subtree
        if p.val < root.val and q.val < root.val:
            root = root.left
        # Both nodes in right subtree
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            # Found split point (LCA)
            return root
    
    return None

Problem: Binary Tree Right Side View

def right_side_view(root: TreeNode) -> list[int]:
    """
    Return values of nodes visible from right side
    
    My approach: BFS, take last node of each level
    Time: O(n), Space: O(w)
    """
    if not root:
        return []
    
    from collections import deque
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Last node of level
            if i == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

Graphs

My Graph Aha Moment

I realized graphs are everywhere:

• Social networks (people = nodes, friendships = edges)

• Maps (cities = nodes, roads = edges)

• Dependencies (tasks = nodes, prerequisites = edges)

Graph Representations

# Adjacency List (most common in interviews)
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1],
    3: [1]
}

# Or using defaultdict
from collections import defaultdict

def build_graph(edges: list[list[int]]) -> dict:
    """Build adjacency list from edge list"""
    graph = defaultdict(list)
    
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # For undirected graph
    
    return graph

Core Graph Patterns

Pattern 1: DFS (Depth-First Search)

Template:

def dfs_template(graph, start):
    """
    DFS using recursion
    """
    visited = set()
    
    def dfs(node):
        if node in visited:
            return
        
        visited.add(node)
        
        # Process node
        print(node)
        
        # Visit neighbors
        for neighbor in graph[node]:
            dfs(neighbor)
    
    dfs(start)

# Iterative DFS (using stack)
def dfs_iterative(graph, start):
    """DFS using stack"""
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
        
        visited.add(node)
        print(node)
        
        # Add neighbors to stack
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

Problem: Number of Islands

This was asked in 4 of my interviews:

def num_islands(grid: list[list[str]]) -> int:
    """
    Count number of islands (connected 1s)
    
    My approach: DFS to mark connected land as visited
    Time: O(m * n), Space: O(m * n)
    """
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    islands = 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
        
        # Mark as visited
        grid[r][c] = '0'
        
        # Explore 4 directions
        dfs(r + 1, c)  # Down
        dfs(r - 1, c)  # Up
        dfs(r, c + 1)  # Right
        dfs(r, c - 1)  # Left
    
    # Check each cell
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1
                dfs(r, c)  # Mark entire island
    
    return islands

# Test
grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
print(num_islands(grid))  # 3

Pattern 2: BFS (Breadth-First Search)

Template:

def bfs_template(graph, start):
    """
    BFS using queue
    """
    from collections import deque
    
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        print(node)
        
        # Visit neighbors
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Problem: Shortest Path in Binary Matrix

def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
    """
    Find shortest path from top-left to bottom-right
    Can move 8 directions
    
    My approach: BFS (guarantees shortest path)
    Time: O(n²), Space: O(n²)
    """
    n = len(grid)
    
    # Edge cases
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    from collections import deque
    
    # 8 directions
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1)
    ]
    
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    
    while queue:
        row, col, dist = queue.popleft()
        
        # Reached bottom-right
        if row == n - 1 and col == n - 1:
            return dist
        
        # Explore 8 neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check bounds and validity
            if (0 <= new_row < n and 0 <= new_col < n and
                grid[new_row][new_col] == 0 and
                (new_row, new_col) not in visited):
                
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, dist + 1))
    
    return -1

Problem: Clone Graph

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

def clone_graph(node: Node) -> Node:
    """
    Deep copy a graph
    
    My approach: DFS with hash map to track clones
    Time: O(V + E), Space: O(V)
    """
    if not node:
        return None
    
    clones = {}  # {original: clone}
    
    def dfs(original):
        if original in clones:
            return clones[original]
        
        # Create clone
        clone = Node(original.val)
        clones[original] = clone
        
        # Clone neighbors
        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

Heaps (Priority Queues)

When I Use Heaps

Heaps are perfect for:

• Finding kth largest/smallest

• Merging k sorted lists

• Top K frequent elements

Heap Operations in Python

import heapq

# Min heap (default)
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)
smallest = heapq.heappop(min_heap)  # 2

# Max heap (negate values)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
largest = -heapq.heappop(max_heap)  # 5

# Heapify list
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)  # O(n)

Heap Problems

Problem: Kth Largest Element

def find_kth_largest(nums: list[int], k: int) -> int:
    """
    Find kth largest element
    
    My approach: Min heap of size k
    - Maintain k largest elements
    - Top is kth largest
    
    Time: O(n log k), Space: O(k)
    """
    import heapq
    
    # Build min heap of size k
    heap = nums[:k]
    heapq.heapify(heap)
    
    # Process remaining elements
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    
    return heap[0]

# Alternative: Using Python's nlargest
def find_kth_largest_v2(nums: list[int], k: int) -> int:
    """One-liner using heapq.nlargest"""
    return heapq.nlargest(k, nums)[-1]

# Test
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5

Problem: Top K Frequent Elements

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """
    Find k most frequent elements
    
    My approach: Hash map + heap
    Time: O(n log k), Space: O(n)
    """
    from collections import Counter
    import heapq
    
    # Count frequencies
    count = Counter(nums)
    
    # Use heap to get top k
    return heapq.nlargest(k, count.keys(), key=count.get)

# Test
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))  # [1, 2]

Problem: Merge K Sorted Lists

def merge_k_lists(lists: list[ListNode]) -> ListNode:
    """
    Merge k sorted linked lists
    
    My approach: Min heap with (value, list_index, node)
    Time: O(N log k) where N is total nodes
    Space: O(k)
    """
    import heapq
    
    dummy = ListNode(0)
    current = dummy
    
    # Initialize heap with first node from each list
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    
    # Process heap
    while heap:
        val, i, node = heapq.heappop(heap)
        
        current.next = node
        current = current.next
        
        # Add next node from same list
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

Key Takeaways

From solving 150+ tree and graph problems:

1. Trees: Master BFS and DFS—they solve 90% of tree problems

2. BST: Remember the inorder property (sorted order)

3. Graphs: BFS for shortest path, DFS for connectivity

4. Heaps: When you need top/bottom K elements

5. Always draw: Visualize before coding

Practice Problems

Must-solve problems I recommend:

Trees:

• Invert Binary Tree

• Serialize and Deserialize Binary Tree

• Path Sum II

• Lowest Common Ancestor

Graphs:

• Course Schedule (Cycle Detection)

• Word Ladder

• Pacific Atlantic Water Flow

Heaps:

• Find Median from Data Stream

• K Closest Points to Origin

What's Next?

In Part 5: Dynamic Programming and Interview Success, we'll cover:

• Dynamic programming patterns and strategies

• Common DP problems with Python solutions

• Final interview preparation tips

• Mock interview best practices

DP is the final frontier—let's conquer it together!

---

This part is based on my experience solving tree and graph problems at companies like Amazon and Microsoft.