Trees
The problem
Many real structures are hierarchical, not flat — a file system, an HTML document, a company org chart — and need a data structure that represents 'contains' and 'parent of' relationships directly, with fast search when the hierarchy is kept ordered.
Why now
Graph theory already defined trees abstractly (a connected, acyclic graph); this topic makes that abstraction concrete as a data structure you build with code, and adds the specific technique — keeping nodes ordered — that turns a tree into a search structure faster than scanning a flat list.
Mental model
A tree is a recursive structure: a node holding a value plus references to child trees, all the way down to empty. That recursive shape is exactly why tree algorithms are almost always recursive functions — the function calls itself on a child, which is itself a smaller tree. A balanced binary search tree keeps left-smaller, right-larger at every node, so search discards half the remaining tree at each step, exactly like binary search.
Requires
- Graph Theory BasicsMathematical Thinking
A tree is formally defined as a connected, acyclic graph; every tree algorithm (traversal, search) is a specialization of a general graph algorithm to this restricted shape.
- RecursionProgramming Fundamentals
A tree's own definition is recursive (a node plus subtrees); nearly every tree operation is naturally written as a recursive function that mirrors that structure.
Helps
- Logarithms & ExponentsMathematical Thinking
A balanced tree's O(log n) height and search time is a direct consequence of repeated halving — the same intuition logarithms already built.
Unlocks
- The DOM as a TreeBrowser Internals
- Graph AlgorithmsComputer Science Fundamentals
- Heaps & Priority QueuesComputer Science Fundamentals
- TriesComputer Science Fundamentals
- Indexes & Query PerformanceDatabase Engineering
- Storage Engines: B-Tree vs. LSM-TreeDatabase Engineering
- DNSNetworking
- File Systems & I/OOperating Systems
- The Virtual DOM & ReconciliationReact
Used in
- The DOM (a tree of HTML elements)
- File systems (directories containing files and directories)
- Database indexes (B-trees power most relational database indexes)
- Binary search trees, heaps, and tries across countless algorithms
Projects
- Implement a binary search tree with insert, search, and in-order traversal from scratch
- Write all three traversal orders (pre-order, in-order, post-order) recursively and explain when each is useful
Examples
- A balanced BST with 1,000,000 nodes has height ~20 — the same log₂(n) bound as binary search
- document.body is the root of the DOM tree; document.body.children walks one level of it
Resources
- Trees — MIT 6.006course
Mastery checklist
- I can implement a binary search tree with insert and search
- I can write pre-order, in-order, and post-order traversal recursively
- I can explain why a balanced tree gives O(log n) search and an unbalanced one can degrade to O(n)
- I can identify a real system's hierarchy (DOM, file system) as a tree and name its root, parents, and leaves