Tree Traversal Target: 15s
BST's ordering invariant enables O(log n) search. But it must hold for entire subtrees, not just direct children.
BST vs BINARY TREE — KEY DIFFERENCES
─────────────────────────────────────
BINARY TREE: BST:
No ordering constraint left < root < right (all nodes)
Search: O(n) Search: O(h), avg O(log n)
Insert: append anywhere Insert: find correct position
Inorder: no special order Inorder: SORTED output
BST INVARIANT (must hold for ENTIRE subtree):
Every node in left subtree < root
Every node in right subtree > root
(Not just immediate children!)
BST OPERATIONS & COMPLEXITY:
Search: O(h) → go left if target < node, else right
Insert: O(h) → search for position, add leaf
Delete: O(h) → 3 cases: leaf, 1 child, 2 children
Min/Max: O(h) → leftmost / rightmost node
Inorder: O(n) → sorted traversal
BALANCED BST: h = O(log n) → all ops O(log n)
SKEWED BST: h = O(n) → degenerates to linked listType it from memory. Go.