Trees

A tree is a hierarchy of nodes where each has one parent and zero or more children; the top is the root, nodes with no children are leaves. The mental hook: anything with nesting is a tree — file systems, the DOM, abstract syntax trees in compilers, org charts, decision processes. The important specialisations: binary search trees (BST) keep values ordered for O(log n) search/insert when balanced (AVL, red-black trees are the classic self-balancing versions); B-trees are multi-way balanced trees used by every relational database for indexes because they minimise disk reads (each node holds many keys, tree is shallow); tries are character-indexed trees for prefix search; heaps are trees maintaining a heap property. Tree traversal comes in three flavours (pre-order, in-order, post-order for DFS; level-order for BFS) — the shape you pick determines the operation's semantics.