Stage 1 · Code
Linked Lists & Trees
BST Operations
Binary Search Trees unlock O(h) search, insertion, and deletion — exploit the invariant that left < root < right for ordered operations.
BST Property
A Binary Search Tree is a binary tree where every node satisfies: all values in the left subtree < node value < all values in the right subtree. This invariant enables O(log n) operations on a balanced tree. The hardest part of BST problems is often not the algorithm itself — it's correctly handling edge cases like duplicate values, null children, and the min/max constraints that propagate through recursive validation.
Template Code
Recursive vs Iterative
Search is naturally iterative — just follow the invariant. Insert and delete are easier to reason about recursively because you need the parent context. For validate, both approaches work; the inorder traversal with a prev pointer is the cleanest.
When to Use
- Ordered data: You need sorted iteration, range queries, or predecessor/successor lookups.
- Dynamic ordering: Elements are inserted/deleted frequently and you need O(log n) operations.
- Validation: Given a binary tree, determine if it respects the BST invariant (LeetCode 98).
- Kth element: BSTs support O(h + k) kth smallest/largest via inorder traversal (LeetCode 230).
- Common ancestor: The BST invariant pinpoints LCA in a single pass — no ancestor stack needed (LeetCode 235).
- Not for: Unordered data, datasets that don't fit in memory (use B-tree), or when balancing overhead matters (use skip list).
Problems
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.