Trees & Graphs

Trees and graphs are among the most frequently tested data structures. They test your ability to think recursively and traverse complex structures.

Binary Trees

A binary tree is a tree where each node has at most two children. The three fundamental traversals:

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

# Inorder: Left -> Root -> Right (gives sorted order in BST)
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Preorder: Root -> Left -> Right (used for serialization)
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Postorder: Left -> Right -> Root (used for deletion)
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

Key Tree Problems in Interviews:

Problem	Approach	Complexity
Maximum depth	DFS recursive	O(n)
Same tree check	DFS compare	O(n)
Invert binary tree	DFS swap children	O(n)
Lowest common ancestor	DFS	O(n)
Validate BST	Inorder traversal	O(n)
Level-order traversal	BFS with queue	O(n)

# Maximum depth of binary tree
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

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

Graphs

Graphs are networks of nodes (vertices) connected by edges. They can be:

• Directed or Undirected
• Weighted or Unweighted
• Cyclic or Acyclic

Representation:

# Adjacency list (most common in interviews)
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D', 'E'],
    'D': [],
    'E': []
}

# Edge list
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('C', 'E')]

DFS and BFS for Graphs:

# DFS (recursive)
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# BFS (iterative with queue)
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

Topological Sort

Used for dependency resolution (course scheduling, build systems):

def topological_sort(graph):
    # Calculate in-degrees
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # Start with nodes that have no dependencies
    queue = deque([n for n in in_degree if in_degree[n] == 0])
    result = []

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

    # If result doesn't include all nodes, there's a cycle
    return result if len(result) == len(graph) else []

Interview Tip: When you see "dependencies," "prerequisites," or "ordering" in a problem, think topological sort.

---

Next, we'll cover heaps and advanced data structures that appear in Top-K and priority-based problems. :::