Handbooks / Data Structures & Algorithms / Chapter 4

Trees and Graphs

7 pages · ~5 min✓ Reviewed

Builds on Sorting and Searching. Next up: Dynamic Programming and Greedy.

Data Structures & AlgorithmsPage 1

Binary Trees, BSTs and Traversals

1. Definition

Binary tree: at most 2 children per node
Height h = longest root-to-leaf path
BST: left subtree < node < right subtree, for every node

2. Mechanism

Search, insert, delete walk one path = O(h)
Balanced: O(log n). Skewed: O(n)
Delete with 2 children: use the inorder successor

3. Traversals

Order	Visit	Use
Preorder	node, left, right	copy a tree
Inorder	left, node, right	sorted BST
Postorder	left, right, node	delete, heights
Level-order	`queue`	by depth

python

def inorder(n):
    if n:
        inorder(n[1])
        print(n[0])
        inorder(n[2])
inorder((2,(1,None,None),(3,None,None)))

root 2, children 1 and 3

output

1
2
3

4. Mistakes

Checking a node against children only: pass min/max bounds down
Inserting sorted data: the BST becomes a linked list
Skewed trees hit the recursion limit

Data Structures & AlgorithmsPage 2

Heaps and Tries

1. Heap

Complete tree; parent <= children (min-heap) or >= (max-heap)
Array: children 2i+1, 2i+2; parent (i-1)//2
push: append, sift up, O(log n)
pop: swap root with last, sift down, O(log n)
peek O(1); heapify n items O(n)

2. Compare

	Heap	BST	Trie
Min peek	O(1)	O(h)	n/a
Search	O(n)	O(h); O(log n) if balanced	O(L)
Sorted?	no	inorder	no

3. Examples

Top-k largest: min-heap of size k, pop when over k, O(n log k)
Trie node: children[char] + is_end; one char per step

python

for x in nums:
    heappush(h, x)
    if len(h) > k:
        heappop(h)

python

for ch in word:
    node = node.kids.setdefault(ch, Node())
node.is_end = True

4. Mistakes

heapq is min-only: push -x for a max-heap
Heap array is not sorted; only the root is ordered
No is_end: 'app' matches when only 'apple' was inserted
Tries use lots of memory

Data Structures & AlgorithmsPage 3

Graph Representations, BFS and DFS

1. Graph and Storage

Graph = vertices V + edges E
Edges: directed or undirected, weighted or unweighted
Adjacency list: O(V+E) space; matrix: O(V^2) space

	List	Matrix
Best for	sparse	dense
Neighbours	O(deg)	O(V)
Edge exists?	O(deg)	O(1)

2. BFS vs DFS

	BFS	DFS
Uses	queue + visited	recursion or stack
Order	level by level	deep first
Gives	shortest path, unweighted	cycles, components, path exists
Time	O(V+E)	O(V+E)

BFS: mark seen when you push, not when you pop

python

q = deque([s]); seen = {s}
while q:
    u = q.popleft()
    for v in adj[u]:
        if v not in seen:
            seen.add(v)
            q.append(v)

BFS skeleton

3. Mistakes

Marking visited on pop: duplicates enter the queue
No visited set on a cyclic graph: infinite loop
One start node only: misses disconnected components
BFS distances on a weighted graph

Data Structures & AlgorithmsPage 4

Topological Sort and Dijkstra

1. Definitions

Topological sort: DAG order, every edge u->v puts u first
Exists only if there is no cycle
Dijkstra: single-source shortest paths, non-negative weights

2. Mechanism

Indegreescount per node
Queue 0sindegree 0
Popdecrement neighbours
Queue new 0sreached 0

Kahn's is O(V+E); fewer than V output = cycle
Dijkstra: min-heap of (dist,node), pop smallest
Skip the entry if its popped dist is stale
Relax: dist[v]=min(dist[v],dist[u]+w)
Dijkstra costs O((V+E) log V)

3. Example

Graph	Result
A->B->C prerequisites	order A, B, C
A-(1)->B-(2)->C, A-(5)->C	dist[C] = 3, not 5

4. Mistakes

Negative edges in Dijkstra: use Bellman-Ford
No stale check when the heap uses lazy deletion
Expecting a topological sort of a cyclic graph
DFS version outputs reverse postorder

Data Structures & AlgorithmsPage 5

Union-Find (Disjoint Set Union)

1. Model and Mechanism

Disjoint sets in a parent array; parent[x]==x marks a root
find(x) gives the root; union(a,b) merges sets

Path compression: parent[x]=find(parent[x])
Union by size: smaller tree under larger
Together: amortized O(α(n)), near constant

python

def find(x):
    if parent[x] != x: parent[x] = find(parent[x])
    return parent[x]
def union(a, b):
    a, b = find(a), find(b)
    if a == b: return False
    if size[a] < size[b]: a, b = b, a
    parent[b] = a; size[a] += size[b]; return True

2. Use and Kruskal

	Union-find	Rerun BFS/DFS
Edge added: connected?	O(α(n))	O(V+E) each time
Split sets, delete edges	No	Rebuild

Sort edges by weight
Keep an edge only if find(u)!=find(v), then union
Equal roots: edge closes a cycle

3. Mistakes

union on raw nodes, not find() roots
No compression and no union by size: find is O(n); size alone gives O(log n)
parent[i] not set to i

Data Structures & AlgorithmsPage 6

Trees and Graphs Cheat Sheet

1. Complexities

Operation	Cost
BST ops	O(h): log n balanced, n skewed
Heap push / pop	O(log n)
Heap peek / heapify	O(1) / O(n)
Trie ops	O(L)
BFS, DFS, Kahn's	O(V+E)
Dijkstra	O((V+E) log V)
Union-find	O(alpha(n))

2. Picks

Need	Pick
Sorted BST output	inorder
Copy a tree	preorder
Delete a tree	postorder
Level by level	level-order (queue)
Top-k, priority queue	heap
Prefix search	trie
Sparse / dense graph	list / matrix
Unweighted shortest path	BFS
Non-negative weights	Dijkstra
DAG ordering	Kahn's or DFS
Connectivity, Kruskal	union-find

3. Pre-submit checks

BST: min/max bounds passed down
BFS: visited marked on push
Loop over every start: disconnected components
Dijkstra: no negative edges
Topological sort: fewer than V output means cycle
Union-find: union applied to roots, not raw nodes

Remember

BST cost is O(h), never plain O(log n).

Data Structures & AlgorithmsPage 7

Check yourself

A validator only checks left.val < node.val < right.val at each node. Tree: 5, with left child 3, whose right child is 7. Does it pass, and is it a BST?

It passes: 3<5 and 7>3.
But 7 is in 5's left subtree, so it is not a BST.
Pass min/max bounds down instead.

Kahn's algorithm runs on edges A->B, B->C, C->B, A->D. What is output?

Only A has indegree 0, then D frees up: output A, D.
B and C wait on each other, so 2 of 4 nodes come out.
Fewer than V nodes means a cycle.

You insert only 'apple' into a trie, but search('app') returns True. What is the bug?

Search returns True after walking the characters, without checking is_end.
'app' is only a prefix, and is_end is False there.