Structures that branch instead of running in a line. This is the hardest stage in the roadmap and deserves the extra time.
This is where most people slow down. Budget the time honestly, and if you fall behind, take the extra weeks here rather than skipping ahead — everything in weeks 30 to 35 leans on this material.
Why this stage exists
Trees and graphs are how you represent anything with structure rather than sequence: file systems, web pages, dependencies, road networks, social connections. They are also where the you practised in week 14 finally earns its keep.
NeetCode 150 · complete category
Graphs practice lab
Model the problem as nodes and edges, then choose the traversal that matches the question: flood-fill for regions, ordering for dependencies.
2 problems
Pattern first
Traversal is bookkeeping about where you have already been
Naive
Re-walking neighbours without marking them revisits the same nodes forever.
Why this works
Marking a node the moment you reach it makes every node and edge cost work exactly once, so a traversal is O(V + E).
Picture itA surveyor lands on unmapped ground, floods the whole landmass with dye, and only then looks for the next unmapped square.
Conceptual blueprint
Scan every cell; on unvisited land, add one to the count and sink its entire connected region before scanning on.
Animated dry-runFrame 1
1 / 8
01
11
20
30
41
50
60
71
80
90
100
111
The grid is drawn row by row: index 0 is r0c0, index 4 is r1c0, index 11 is r2c3.
islands0layout3 rows × 4 cols, row-major
1def num_islands(grid):
2 rows, cols = len(grid), len(grid[0])
3 islands = 0
4 def sink(r, c):
5 if r < 0 or c < 0 or r == rows or c == cols or grid[r][c] == "0":
6 return
7 grid[r][c] = "0"
8 for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
9 sink(r + dr, c + dc)
10 for r in range(rows):
11 for c in range(cols):
12 if grid[r][c] == "1":
13 islands += 1
14 sink(r, c)
15 return islands
Check yourself before reading onCost it first
Sinking the grid in place costs you something. What?
Find the bug
Why does this hit a recursion limit on any two adjacent 1s?
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
islands = 0
def sink(r, c):
if r < 0 or c < 0 or r == rows or c == cols or grid[r][c] == "0":
return
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
sink(r + dr, c + dc)
grid[r][c] = "0"
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
sink(r, c)
return islands
Predict the next step
sink is standing on r1c0. Which of its four neighbours can it still sink?
Fill in the blanks
Recall each hidden line before revealing it. 3 left.
1def num_islands(grid):
2 rows, cols = len(grid), len(grid[0])
3 islands = 0
4 def sink(r, c):
5
6 return
7
8 for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
9 sink(r + dr, c + dc)
10 for r in range(rows):
11 for c in range(cols):
12 if grid[r][c] == "1":
13
14 sink(r, c)
15 return islands
Why the naive approach falls short
Ask of each land cell which island it belongs to, comparing it against every previously seen cell.
Why the optimized approach works
Sinking a region on discovery guarantees that a later scan can never re-enter it, so each island is counted exactly once.
Time
O(rows × cols) — every cell is visited by the scan and sunk at most once.
Space
O(rows × cols) — one big snaking island puts every cell on the call stack.
NeetCode 150 · complete category
Trees practice lab
A tree problem is nearly always the same shape: do something at this node, then trust the same function on its children.
2 problems
Pattern first
Recursion mirrors the structure
Naive
Trying to reach every node with loops forces you to hand-manage a stack of unfinished branches.
Why this works
A subtree is a smaller tree of the same kind, so a function that handles one node and delegates the rest is already complete.
17 return max(best.values()) if len(best) == n else -1
Check yourself before reading onCost it first
Why must a node be skipped when it is popped a second time?
Find the bug
A plain queue replaces the heap. When does this give the wrong answer?
from collections import deque
def network_delay(times, n, start):
graph = {node: [] for node in range(1, n + 1)}
for source, target, weight in times:
graph[source].append((target, weight))
best = {}
queue = deque([(0, start)])
while queue:
elapsed, node = queue.popleft()
if node in best:
continue
best[node] = elapsed
for target, weight in graph[node]:
queue.append((elapsed + weight, target))
return max(best.values()) if len(best) == n else -1
Predict the next step
The queue holds (1, n1) and (1, n3). What is popped next?
Fill in the blanks
Recall each hidden line before revealing it. 3 left.
17 return max(best.values()) if len(best) == n else -1
Why the naive approach falls short
Recompute every path from the source and keep the best, which revisits shared prefixes endlessly.
Why the optimized approach works
Since every weight is non-negative, no later route can undercut the cheapest entry currently on the heap.
Time
O(E log V) — each edge can push one heap entry.
Space
O(V + E) — the graph, the settled map, and the queue.
What you are learning — 7 topics
Trees and binary trees
A tree is a set of things that branch from one starting point, with one path down to each thing.
Reach for it whenUse a tree instead of a list when the data has parent-child levels or choices that split; use a graph when a thing can have several parents or links can loop.
Think of it likeThe folders on your computer. One folder contains others, which contain others, and no folder contains its own parent.
The vocabulary is worth getting straight once. The thing at the top is the root. Each thing is a node. A node directly below another is its child; the one above is its parent. A node with no children is a leaf. Depth is how many steps from the root, and height is the longest path from the root down to any leaf.
A binary tree limits every node to at most two children, called left and right. That restriction makes the maths tractable, which is why almost all the theory is about specifically.
Syntax you can use
class Node:
def __init__(self, value):
self.value = value
self.left = self.right = None
Inorder traversal, which visits a BST in sorted order.
Notice that each node below the root has exactly one incoming parent edge, so its path from the root is unique.
Several ways to see it
Its shapeEvery child has one route from the root
A tree forbids cycles and gives each non-root node exactly one parent. That unique route makes ancestry, depth, subtree, and leaf precise rather than metaphorical.
What the machine doesTraversal order is a scheduling choice
Preorder acts before visiting children, inorder acts between binary children, and postorder acts after them. The node storage is unchanged; only the moment you schedule the node's work moves.
How it breaksDepth turns into memory even when visits stay linear
A recursive traversal of a balanced tree holds frames, but a chain-shaped tree holds O(n). The still visits each node once while its stack requirement becomes dangerous.
In the wild
Browser DOM — represents an HTML document as parent and child nodes that rendering and selectors walk.
Git — stores directory snapshots as tree objects whose entries point to blobs or more trees.
Commonly gets misread as
"Every branching structure is a tree." Correction: a tree has no cycles and each non-root node has one parent.
"Binary means every node has two children." Correction: it means at most two.
What it costsVisiting every node is O(n). Operations that walk from root to leaf cost O(height), which is O(log n) when balanced and O(n) when not.
A keeps smaller values on one side and larger values on the other, turning order into a route.
Reach for it whenUse a balanced search tree instead of a when you need ranges, nearest values, or sorted iteration; use a hash table for exact key lookup only.
Searching works like the number-guessing game you wrote in week 2. Compare with the current node, go left or right, repeat. Each step discards half of what remains, so the cost is the height of the tree.
That last clause carries all the risk. If you insert values in sorted order, every new item goes to the right of the last one and the tree degenerates into a — height n, searching O(n), every advantage gone. A tree is only fast when it is balanced, and nothing about the basic version guarantees that.
Syntax you can use
if value < node.value:
node = node.left
else:
node = node.right
Chooses the left or right subtree using the BST ordering rule.
while node is not None:
Searches down a tree until it finds a value or reaches an empty child.
if value == node.value:
return node
Stops a BST search when the target is found.
node = node.left
Moves toward smaller values in a binary search tree.
Notice that every left subtree is smaller and every right subtree is larger; one violated edge corrupts later searches.
Several ways to see it
What the machine doesEvery comparison discards one whole subtree
At a node, a smaller key can only be left and a larger key can only be right. Search follows one child, so untouched branches need no inspection as long as the ordering invariant holds.
What it costsHeight, not node count, sets the operation cost
Search, insertion, and deletion take time proportional to the root-to-leaf path. Balanced height is logarithmic; sorted insertion into a plain BST can make height equal to n.
How it breaksDeletion has one genuinely structural case
A leaf simply disappears and a one-child node can be bypassed. A two-child node must be replaced by its next or previous ordered neighbour, then that replacement must be removed from its old position.
In the wild
Java TreeMap — uses a red-black search tree to keep keys ordered while supporting lookup and range views.
C++ std::map — provides an ordered associative container, commonly implemented as a red-black tree.
Commonly gets misread as
"A search tree is automatically fast." Correction: an unbalanced tree can collapse into a linear chain.
"It beats a hash table for exact lookup." Correction: its advantage is order and ranges, not average lookup speed.
What it costsSearch, insert and delete are O(log n) when balanced, and O(n) when the tree has degenerated.
A balanced tree rearranges itself so no search is forced down one long, lopsided branch.
Reach for it whenUse a balanced tree instead of a plain BST when updates arrive in unknown order and predictable lookup matters; use a hash index when ranges and sorted order do not.
An AVL tree and a red-black tree both fix the balance problem by performing rotations — small local rearrangements that reduce height — whenever an insert or delete makes the tree too lopsided. The details differ; the purpose is identical.
B-trees are the interesting ones. They are wide and shallow, with each node holding many keys and many children rather than two. That shape exists because reading from a disk is thousands of times slower than reading from memory, so you want to minimise the number of separate reads, not the number of comparisons. A wide tree is shallow, and shallow means fewer disk reads.
Syntax you can use
height = 1 + max(left_height, right_height)
Computes a node's height from its children.
balance = left_height - right_height
Computes the AVL balance factor for a node.
if abs(balance) > 1:
node = rebalance(node)
Repairs an AVL node whose two sides differ too much in height.
return rotate_left(node)
Performs a rotation to shorten a right-heavy subtree.
Notice that rotation preserves the inorder sequence 1, 2, 3 while moving 2 upward to cut the height.
Several ways to see it
Why it existsSorted inserts exposed the plain tree's missing guarantee
A BST promised fast navigation only when its height happened to stay small. AVL and red-black trees added local rules and rotations so insertion order could no longer stretch the structure into a chain.
What the machine doesA rotation changes height without changing order
Rotations move a parent-child relationship and transfer one middle subtree. An inorder traversal returns exactly the same sorted keys before and after, while the longest path becomes shorter.
Against the alternativeDatabases balance pages, not individual keys
B-trees and B+ trees give each node many children so one disk page holds many separators. Fewer, wider levels mean fewer storage reads than a binary tree would require for the same number of records.
In the wild
PostgreSQL B-tree index — keeps index pages balanced so equality and range scans reach keys through a shallow path.
Java TreeMap — rotates and recolors its red-black tree after updates to keep operations logarithmic.
Commonly gets misread as
"Balanced means both sides contain exactly the same number of nodes." Correction: it only bounds how far heights can drift.
"Rebalancing sorts the whole tree again." Correction: local rotations repair the affected path.
What it costsAll operations stay O(log n), because the height is kept bounded by construction.
A heap is a partly ordered pile built to reveal the smallest or largest item without sorting everything.
Reach for it whenUse a heap instead of a sorted list when items arrive continuously and you repeatedly need the next best or top k; use sorting when you need the entire final order.
Think of it likeA tournament bracket. The winner is at the top; you know who is best without knowing the full ranking of everybody else.
The rule is simply that every parent beats its children — smaller in a min-heap, larger in a max-heap. Nothing is claimed about siblings, which is why a heap is much cheaper to maintain than a fully sorted structure.
The clever part is that it is stored in a plain , with no node objects and no references at all. The children of position i live at 2i+1 and 2i+2. Arithmetic replaces , which makes it compact and fast.
Syntax you can use
import heapq
Imports Python's min-heap tools.
heap = [3, 1, 4]
heapq.heapify(heap)
Turns a list into a min-heap in place.
heapq.heappush(heap, item)
Adds an item while keeping the smallest item at heap[0].
smallest = heapq.heappop(heap)
Removes and returns the smallest item.
heapq.heappush(heap, (-priority, item))
Uses negative priorities when you need a max-heap.Tuples break ties with their next item. Add a counter if equal priorities contain values Python cannot compare.
Notice that parent and child positions are arithmetic on one dense array, so no node pointers are needed.
Several ways to see it
Its shapeA complete tree fits inside an array without pointers
Level-order placement makes a node at index `i` find children at `2i + 1` and `2i + 2`. Completeness prevents interior gaps, so the array representation stays dense.
What the machine doesRepair travels along one path
Insertion places a value at the next open leaf and swaps it upward while it outranks its parent. Removal replaces the root with the last value and sifts it down, touching only one root-to-leaf path.
Against the alternativeA heap exposes the winner, not the full ranking
Use a heap when you repeatedly need the smallest item among changing candidates. A sorted list makes every item ordered but pays to shift on insertion; a heap keeps only enough order for the next winner.
In the wild
Lucene TopScoreDocCollector — keeps competitive search hits in a while collecting top-scoring documents.
Python asyncio — keeps delayed callbacks in a heap ordered by their scheduled time.
Commonly gets misread as
"A heap is fully sorted." Correction: only each parent-versus-child relationship is guaranteed.
"Finding any value is logarithmic." Correction: only the top is direct; an arbitrary search is linear.
What it costsAdding and removing the top are O(log n). Looking at the top is O(1). Building a heap from an existing list is O(n).
A stores words by sharing their beginnings, so each next character chooses the next branch.
Reach for it whenUse a trie instead of a hash table for prefix lookup, autocomplete, or longest-prefix matching; use a hash table for exact whole-key lookup with less overhead.
Think of it likeYour phone keyboard narrowing its suggestions as you type each letter. Typing c-a-t walks three steps down.
The remarkable property is that looking a word up depends only on the length of that word, not on how many words are stored. Searching a million-word dictionary for a five-letter word takes five steps.
It also gives you prefix search for free, which a hash table cannot do at all. “Every word starting with pre” means walking to the pre node and collecting everything below it.
Syntax you can use
node = {}
Uses a dictionary as one trie node, mapping characters to children.
node = node.setdefault(char, {})
Follows a character edge, creating it if it is new.
node["$"] = True
Marks that a complete word ends at this node.
for char in word:
if char not in node:
return False
node = node[char]
Follows a word through a trie and fails as soon as a prefix is absent.
Notice how car and cat share two nodes; the structure stores common prefixes once and branches only where letters differ.
Several ways to see it
Its shapeShared prefixes occupy one shared path
Words `car`, `cart`, and `cat` reuse the `c` and `a` nodes before branching. An end marker distinguishes a complete word from a prefix that merely leads to longer words.
What it costsLookup depends on key length, not dictionary size
Finding a word follows one edge per character, so the work is O(k) for a key of length k. The trade is memory: nodes and child maps can cost far more than storing the words compactly.
Against the alternativeA hash table answers equality; a trie answers continuation
A hash table is usually smaller and faster for exact membership. A trie earns its cost when the query is 'what begins with this prefix?' or when results must continue character by character.
In the wild
Linux IPv4 routing — uses an LC-trie to perform longest-prefix route lookup.
Lucene term dictionary — uses a finite-state transducer that shares term prefixes while mapping terms to index metadata.
Commonly gets misread as
"A trie stores every word separately." Correction: words with the same prefix share nodes.
"It is always more memory-efficient than a hash table." Correction: sparse child links can cost substantial memory.
What it costsInsert and search are O(length of the word), regardless of how many words are stored.
A graph is a collection of things and the direct relationships between them, with no required hierarchy.
Reach for it whenUse a graph instead of a tree when relationships can cross, cycle, or give one item several parents; use a table when connections are not part of the questions you ask.
Think of it likeA map of cities joined by roads. Or people joined by friendships, or web pages joined by links.
The things are and the connections are edges. Four properties describe any graph. Directed means edges go one way — following someone on social media. Undirected means both ways — being friends. Weighted means edges carry a number, like distance or cost. Cyclic means you can go round in a circle and end up where you started.
There are two ways to store one. An keeps, for each vertex, a list of what it connects to — compact when most things are not connected to most other things, which is nearly always. An adjacency matrix keeps a full grid of every possible pair, which makes checking a single connection instant but uses space proportional to the square of the vertex count. Use the list unless you have a specific reason not to.
Syntax you can use
graph = {"A": ["B", "C"], "B": []}
Represents a graph as an adjacency list.
graph[a].append(b)
Adds a directed edge from a to b.
graph[b].append(a)
Adds the reverse edge too, for an undirected graph.
for neighbour in graph[node]:
Visits each edge leaving a node.
Notice that B has two routes back to A; the cycle is exactly why traversal must remember visited vertices.
Several ways to see it
Its shapeA graph keeps relationships without forcing a hierarchy
Vertices may have many incoming and outgoing edges, and cycles are allowed. Direction and edge weight add meaning, but neither creates a root or a unique path.
Against the alternativeAdjacency lists pay for edges that exist
A list or set of neighbours uses O(V + E) space and iterates actual connections efficiently. A matrix spends O(V squared) space but answers whether a specific edge exists with one indexed lookup.
How it breaksTraversal needs a visited set because routes can return
Without marking vertices, a cycle sends DFS or BFS around forever and multiple paths repeat work. Mark on discovery, not later on removal, when duplicate frontier entries would be expensive.
In the wild
npm — resolves packages and their version constraints as a dependency graph.
Neo4j — stores nodes and relationships directly so queries can traverse connected data.
Commonly gets misread as
"A graph must look visual." Correction: adjacency lists and tables can represent it entirely in data.
"Every pair of nodes has a path." Correction: graphs can contain disconnected components.
What it costsAdjacency list: O(vertices + edges) space, and checking one specific connection costs O(number of neighbours). Adjacency matrix: O(vertices squared) space, and checking one connection is O(1).
Union-find keeps track of which items have become part of the same group as groups merge.
Reach for it whenUse union-find instead of repeated graph searches when the only questions are 'connect these' and 'are these connected?'; use BFS or DFS when you need the actual path.
Think of it likeWorking out which islands are joined once bridges are built. You do not care about the route, only whether two places are now connected.
Two operations. Find tells you which group something belongs to. Union merges the groups containing two things. Each group is a tree, and the root of that tree is the group's name.
Two small optimisations make it almost free. Path compression flattens the tree every time you do a find, pointing everything directly at the root. Union by rank always attaches the shorter tree under the taller one so things stay flat. Together they bring the cost so close to constant that the difference is not worth describing.
Syntax you can use
parent = list(range(n))
Starts n separate groups, each item its own parent.
Finds a group's root and compresses the path for later calls.
root_a, root_b = find(a), find(b)
Finds the representative of each group before comparing or merging.
parent[root_b] = root_a
Merges two different groups by attaching one root to the other.
Notice that all four items share root A after compression; shorter parent paths make later connectivity checks almost immediate.
Several ways to see it
Its shapeEach component is a tree whose root is its name
Every item points upward to a parent, and a root points to itself. Two items are connected exactly when repeated parent links lead to the same representative root.
What the machine doesPath compression rewrites history during lookup
A find operation first climbs to the root, then makes visited nodes point much closer or directly to it. Future finds become cheaper even though the represented groups have not changed.
How it breaksArbitrary unions quietly rebuild tall chains
Always attaching one root under another without considering size can make find linear. Union by size or rank keeps the smaller tree below the larger, and path compression makes the amortized cost nearly constant.
In the wild
NetworkX Kruskal MST — uses disjoint sets to reject edges whose endpoints are already connected.
Reading about this stage is not the same as finishing it. Type every one of these from a blank file rather than copying — the writing is the part that teaches.
Build a binary search tree
Insert, search and delete. Delete is genuinely fiddly — a node with two children has to be replaced by its in-order successor. Work through that case carefully rather than copying it.
All four traversals, both ways
In-order, pre-order, post-order and level-order — each written recursively and again with an explicit stack or queue. Eight functions. This is repetitive on purpose: it is what makes tree recursion automatic.
Build a binary heap
Store it in a plain array, with children of position i at 2i+1 and 2i+2. Implement push and pop, then use it to find the ten largest numbers in a list of a million without sorting.
Build a trie
Insert and search, then add a method returning every word beginning with a given prefix. You have built the core of an autocomplete.
Breadth-first and depth-first search on a graph
Store the graph as an adjacency list. Write both traversals, and make sure both keep a visited set. Deliberately run one on a graph with a cycle without the visited set first, so you see it hang — that failure is worth experiencing once.
You are done with this stage when
Exit checkYou can implement a binary search tree with insert and delete, all four traversals both recursively and iteratively, a binary heap, a trie, and breadth-first and depth-first search on an adjacency list — all from a blank file. Around 120 problems solved in total.
If you cannot do this, repeat the stage rather than moving on. Nothing later gets easier by skipping it.
Worth knowing before you start
This stage and dynamic programming in week 33 are where people quit. If you are behind schedule, take the extra weeks here. The timeline is a guide, not a contract.
Rewatching lectures feels like progress and is not. If you have not written code this week, you have not learned anything this week.
This stage corresponds to DSA Phase 3 — Non-Linear Data Structures in the source roadmap.