Unit 04
Trees & Binary Search Trees
A tree organizes data hierarchically: one root, and every other node has exactly one parent. A binary search tree adds a rule about ordering that turns that shape into a fast lookup structure.
// looking for 6: go left of 8, right of 3, found — two steps instead of scanning everything
What it is
A tree is a hierarchy of nodes starting from a single root, where each node can have child nodes beneath it. A binary tree limits each node to at most two children. A binary search tree (BST) adds one rule: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. That rule is what makes searching fast.
Why it's useful
- Fast search, insert, and delete. In a balanced BST, each comparison eliminates roughly half the remaining nodes, similar to binary search.
- Natural for hierarchical data. File systems, organization charts, and parsed expressions all have a tree-like shape already.
- Ordered traversal. Walking a BST in-order visits every value from smallest to largest automatically.
Where it struggles
- Can become unbalanced. If values are inserted in sorted order, a plain BST degrades into something resembling a linked list, losing its speed advantage.
- Keeping it balanced requires extra structures like AVL trees or red-black trees, which add implementation complexity.
Time complexity (balanced BST)
| Operation | Average | Worst case (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |