Trees & Binary Search Trees
A file system has folders inside folders. An org chart has a CEO with reports, who have their own reports. An HTML page has elements nested inside elements. All three are the same shape wearing different clothes: a tree - and once you can see that shape, a whole category of real code stops looking mysterious.
This guide starts with what a tree actually is, then narrows to one specific, hugely useful kind: the binary search tree, which turns the ordering trick from Sorting & Searching, Explained into a data structure you can insert into and search on the fly.
How to read this
Read in order - Phase 2's binary search tree only makes sense once "node," "child," and "leaf" from Phase 1 are second nature.
The phases
- What a Tree Is - nodes, root, children, leaves, and why so many real-world structures turn out to be trees.
- Binary Search Trees - the one ordering rule that makes a tree fast to search and insert into, with real code building one from scratch.
- BST Performance & Gotchas - why a BST is usually
O(log n), how it can silently degrade toO(n), and what fixes that.