P-4.5 Trees and Binary Search Trees
You can implement a binary search tree with insertion, lookup and traversal, explain why its shape decides its performance, and say what balancing achieves.
A search tree keeps data in order while still finding things quickly, which a hash table cannot do. Everything about it depends on shape: a balanced tree gives logarithmic operations and a degenerate one is a linked list. That is why the interesting structures are the self-balancing ones, and why understanding the plain version first makes them comprehensible rather than magical.
Work through these
Trees, and the vocabulary: root, children, leaves, height
A tree is nodes connected without cycles, with one node designated the top. Height is the longest way down from it, and nearly every cost in this topic is stated in terms of height.
The binary search property, and how lookup uses it
Everything smaller sits on one side and everything larger on the other, so each comparison discards half of what is left. That is the whole reason a search tree is faster than a scan.
Algorithms, 4th Edition — companion site · ReferenceInsertion, and how sorted input produces the worst possible shape
Inserting already-ordered values sends every new item down the same side, giving a tree of height equal to its size. The structure has degenerated into a list without ever reporting a problem.
Traversals: in-order, pre-order, post-order, and what each is for
Visiting in order yields the values sorted, which is the property a hash table cannot offer. The other two orders matter for copying, deleting and evaluating structured expressions.
What balancing buys, and what it costs
Self-balancing trees do extra work on every insertion to keep the height logarithmic, which converts an unpredictable worst case into a guaranteed bound. Understanding the guarantee matters more than memorising the rotations.
Sign in to keep your progress.
Free resources
Links last checked 31 Aug 2026.
Stuck here?
Ask a mentor. A real person answers, and they can see exactly which topic you're on. Usually within a couple of working days.
Checking your session…
Topics shown in module order.