Intro

Arrays give you $O(1)$ random access but $O(n)$ search (unless sorted, then $O(\log n)$ with binary search, but insertion becomes $O(n)$).

Linked lists give you $O(1)$ insertion but $O(n)$ search. Binary Search Trees solve this tradeoff.

The BST property ensures that at each node, you know which half contains your target. Search, insert, and delete all take $O(h)$ time, where $h$ is the tree height.

The catch: height depends on insertion order. Insert $[1, 2, 3, 4, 5]$ and you get a stick with $h = n - 1$. Insert in balanced order and $h = O(\log n)$.

In this section, I'll teach you BST operations and the inorder property. You'll see why self-balancing trees (AVL, Red-Black) exist. And when simpler solutions work fine.