Trees

Trees store things so that every step down cuts the search. Walk them in different orders, keep them balanced as they grow, and use them to answer range questions fast. Each one has a live visualizer running the real code.

1. 01Tree traversalsVisit every node before, between or after its children: pre-, in- and post-order.O(n)
2. 02Level-order traversalVisit a tree one level at a time, using a queue.O(n)
3. 03Binary search treeSmaller to the left, bigger to the right, so each step halves the search.O(h)
4. 04Deleting from a BSTRemove a node with zero, one or two children and keep the order intact.O(h)
5. 05AVL treeRotate after every insert so no branch gets more than one level taller.O(log n)
6. 06Red-black treeColour nodes red or black and recolour or rotate to stay roughly balanced.O(log n)
7. 07TrieStore words letter by letter so shared prefixes share a path.O(length)
8. 08Segment treeStore sums of halves, quarters and so on to answer any range sum in log n.O(log n)
9. 09Fenwick treePrefix sums that update in log n, using the lowest set bit of each index.O(log n)