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 26 to 34 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 13 finally earns its keep.
What you are learning — 7 topics
Trees and binary trees
Information arranged in a branching hierarchy: one thing at the top, each thing below belonging to exactly one thing above, and no loops back upwards.
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.
Traversal means visiting every node exactly once. There are four orders and each has a purpose. In-order visits left, then the node, then right — on a search tree this comes out in sorted order. Pre-order visits the node first, then its subtrees, which is what you want in order to copy a tree. Post-order visits children before the node, which is what you want in order to delete one safely. Level-order visits everything one step down, then two steps down, and needs a queue rather than recursion.
Write each traversal recursively first, because the recursive version is four lines and reads like the definition. Then write them with an explicit stack, which is uglier and shows you what the was doing for you.
What it costsVisiting every node is O(n). Operations that walk from root to leaf cost O(height), which is when balanced and O(n) when not.
Where you meet it in real softwareFile systems, the structure of a web page, organisational charts, decision trees in machine learning, the parse trees compilers build from your code.
A binary tree kept in order: everything smaller than a node goes to its left, everything larger goes to its right. That one rule makes searching fast.
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 is only fast when it is balanced, and nothing about the basic version guarantees that.
So why use one rather than a , which is faster? Because a search tree keeps things in order. It can answer “what is the next value after this one”, “give me everything between 10 and 20”, and “walk everything in sorted order”. A hash table cannot do any of those — hashing deliberately destroys ordering.
That is the choice in practice: hash table when you only ever look things up by exact key, search tree when you need ranges or sorted iteration.
What it costsSearch, insert and delete are O(log n) when balanced, and O(n) when the tree has degenerated.
Where you meet it in real softwareOrdered maps and sets, database range queries, anything needing sorted iteration.
Search trees that rearrange themselves as you insert, so they never degenerate into a chain. B-trees are a variant designed for data stored on disk.
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.
This is not an abstraction. B-trees and their close relative B+trees are literally how PostgreSQL, MySQL and the file systems on your computer store their indexes. When someone says a database query is slow because it is missing an index, they mean there is no B-tree for that column, so the database has to read every row.
On depth: understand what a rotation does and why balance matters. Do not memorise red-black deletion cases — that is genuinely low value, and even people who work on databases look them up.
What it costsAll operations stay O(log n), because the height is kept bounded by construction.
Where you meet it in real softwareDatabase indexes in PostgreSQL and MySQL, file systems including NTFS and ext4, the ordered map types in C++ and Java.
A tree arranged so the smallest item is always at the top and cheap to remove. It is not sorted — only the top is guaranteed.
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.
Adding puts the item at the end and bubbles it up while it beats its parent. Removing the top takes the last item, puts it on top, and sinks it down while a child beats it. Both touch only one path from top to bottom, so both are O(log n).
Heaps are the engine inside , and priority queues are the engine inside Dijkstra's shortest-path in week 27. They also solve the top-K problem neatly: to find the ten largest items in a stream of a million, keep a heap of size ten rather than sorting the lot.
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).
Where you meet it in real softwareTask schedulers, Dijkstra's algorithm, top-K queries, event simulation, keeping a running median with two heaps.
A tree for words, where each step down adds one letter, so every path from the top spells a prefix.
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.
The cost is memory. A node per letter per branch adds up, and there are compressed variants that merge single-child chains to reduce it.
Internet routers use this idea for longest-prefix matching on IP addresses, which is how a packet gets pointed at the right next hop.
What it costsInsert and search are O(length of the word), regardless of how many words are stored.
Where you meet it in real softwareAutocomplete, spell-checkers, IP routing tables, predictive text.
Things, and the connections between them. Unlike a tree, connections can point any way and can loop back on themselves.
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.
A tree is just a graph with no cycles and exactly one path between any two points. Arriving at graphs after trees means you already have most of the intuition; what is new is handling cycles, which is why every graph algorithm keeps a visited set. Without one, a cycle makes your program loop forever.
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).
Where you meet it in real softwareSocial networks, road and route networks, package dependency resolution in npm and pip, recommendation engines, network topology.
A structure that tracks which things are in the same group, and can merge two groups almost instantly.
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.
It is small enough to write in about twenty lines and it turns several otherwise-awkward problems into easy ones — detecting cycles, finding connected components, and Kruskal's algorithm in week 29.
What it costsEffectively O(1) per operation once path compression and union by rank are in place.
Where you meet it in real softwareDetecting cycles in a network, building minimum spanning trees, labelling connected regions in an image, working out whether two accounts belong to the same person.
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 31 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.