Core · Module 10
Trees and binary search trees
Hierarchical data, traversals, and keeping keys in order with a binary search tree.
Trees organize data by hierarchy: folders, web pages, parsed programs and, in a binary search tree, sorted keys. This module covers the vocabulary and the traversal orders, the search tree property that lets one comparison discard a whole subtree, inserting and deleting without breaking that property, the three recursive shapes that solve most tree problems, and level-by-level traversal with a queue.
- 1Vocabulary and traversalsPro — members onlyA tree is nodes joined by parent-child links with no cycles. Visiting every node is a choice of order: before the children, between them, or after them. Each order fits different jobs.13 min
- 2Binary search treesPro — members onlyA binary search tree keeps smaller keys to the left of each node and larger keys to the right, so a search discards a whole subtree at every step. Its speed depends entirely on its height.13 min
- 3Insert and deletePro — members onlyInserting into a binary search tree is a search that ends by attaching a node. Deleting is harder when the node has two children: its successor takes its place.14 min
- 4Tree recursion patternsPro — members onlyMost tree problems are solved by one of three recursive shapes: combine the children's answers on the way up, pass information down from the root, or return one value while updating a global best.14 min
- 5Level-order traversalPro — members onlyVisiting a tree level by level needs a queue instead of a stack. Taking a snapshot of the queue's size separates one level from the next, which solves a family of problems about depth, width and views.12 min