Trees and Hierarchical Storage

Branching Structures

A tree stores data hierarchically. It has a single root node at the top; every node may have child nodes, and each node except the root has exactly one parent. Nodes with no children are leaves. Trees model naturally-nested data: file systems, organization charts, the structure of a program, family lineage.

A binary tree restricts each node to at most two children (left and right). The most important variant is the binary search tree (BST), which maintains an ordering invariant: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This invariant makes searching efficient — to find a value, compare it to the root and go left or right, discarding half the remaining tree at each step, exactly like binary search.

When a BST is balanced (its subtrees stay roughly equal in height), search, insertion, and deletion are all $O(\log n)$ — the tree's height is about $\log n$, and each operation walks one path from root to leaf. But a BST can degenerate: inserting already-sorted data makes every node have only one child, producing a tree that is really a linked list of height $n$, and operations degrade to $O(n)$. Self-balancing trees (AVL, red-black) exist precisely to keep the height logarithmic.

Trees are traversed in standard orders: in-order (left, node, right — which visits a BST's values in sorted order), pre-order, post-order, and level-order (breadth-first).

Common pitfall: assuming a binary search tree gives $O(\log n)$ operations no matter what. That holds only when the tree is balanced. Inserting sorted data degenerates the BST into a linked list of height $n$, and operations become $O(n)$ — which is exactly why self-balancing trees exist.

A balanced binary search tree with an accent search path descending from root to a target, halving the visible subtree at each step.

$$\text{balanced height} \approx \log_2 n$$