BST: insert & search
Scenario
Searching an unsorted list takes O(n) time. Binary search on a sorted array takes O(log n), but inserting a new element takes O(n) shift time. How can we get O(log n) search AND O(log n) insertion?
How does a tree structure allow both searching and inserting in log-n time?
Why it exists
Problem: Sorted arrays allow O(log n) search via binary search, but inserting a new item requires O(n) array element shifting. Unsorted lists allow fast insertion but slow O(n) searches.
Naive approach: Using sorted arrays for lookup and re-sorting or shifting array entries on every insert.
Better idea: Use a Binary Search Tree (BST) where left subtree < node < right subtree. Descending the tree halves the search space at each step, achieving O(log n) lookup and dynamic O(log n) pointer-based insertion.
Mental model
Binary search turned into a dynamic pointer tree structure.
At each node, compare the target key to `node.val`. If target is smaller, move to `node.left` (discarding the entire right subtree). If larger, move to `node.right` (discarding the entire left subtree). For insertion, follow this search path until reaching a null child reference, then attach the new node there.
Repeated decision: target vs this node -- go LEFT (smaller) or RIGHT (larger)?
Explanation
A Binary Search Tree (BST) is a binary tree that satisfies the strict BST Ordering Invariant at EVERY node:
- All keys in `node.left` subtree are strictly LESS than `node.val`.
- All keys in `node.right` subtree are strictly GREATER than `node.val`.
Searching in a BST:
1. If `node is None`, target is not present (return None).
2. If `target == node.val`, target found (return node).
3. If `target < node.val`, recurse `search(node.left, target)`.
4. If `target > node.val`, recurse `search(node.right, target)`.
Inserting in a BST:
To insert key `val`:
1. Follow the search path for `val`.
2. When you reach a `None` child slot, create `TreeNode(val)` and attach it to the parent.
3. Insertion always lands at a new leaf node at a unique deterministic spot.
Walkthrough on BST Search and Insert:
Given BST:
8
/ \
3 10
/ \
1 6
Search for target `6`:
- Compare 6 vs 8: 6 < 8 -> go left to 3.
- Compare 6 vs 3: 6 > 3 -> go right to 6.
- Compare 6 vs 6: 6 == 6 -> Found!
Insert target `7`:
- Compare 7 vs 8 -> go left to 3.
- Compare 7 vs 3 -> go right to 6.
- Compare 7 vs 6 -> go right to 6.right (which is None).
- Attach `TreeNode(7)` as 6.right.
The Critical Degradation Caveat (Spindly Tree Trap):
If elements are inserted in already sorted order (e.g. `1, 2, 3, 4, 5`), the BST degrades into a single long line (a linked list). In this worst case, tree height `h = n`, and search/insert cost degrades from `O(log n)` to `O(n)`. Self-balancing BSTs (AVL, Red-Black trees) fix this by rebalancing during insertions.
Key points
- BST Invariant: For every node: max(left subtree) < node.val < min(right subtree).
- Time Complexity: O(h) for search and insert, where h is tree height. O(log n) when balanced; O(n) worst-case when skewed.
- Unique Insertion Spot: Every key has exactly one valid null slot where it can be inserted as a leaf while preserving the BST property.
Pattern: BST Search and Insert
Recognition cues:
- sorted tree property
- halving search space by comparison
- dynamic ordered set
Failure signals
- You need dynamic insertions/deletions while maintaining sorted order.
- You need to quickly query minimum, maximum, predecessor, or successor elements.
Engineering examples
C++ `std::set` / Java `TreeMap`
Maintain a dynamically changing collection of unique items in sorted order with range query support.
Under the hood, `std::set` and `TreeMap` use self-balancing BSTs (Red-Black trees) to guarantee O(log n) insert, search, and delete.
Database B-Tree Indexes
Perform fast disk lookups and range scans on database column keys.
B-Trees are multi-way generalizations of BSTs optimized for block storage, keeping search and insert logarithmic.
When not to use
- Data is already fully static and index lookups are constant: Use a sorted array with binary search if no insertions take place (better cache locality).
- O(1) average lookup is needed without range queries: Use a Hash Map for O(1) key lookups if ordering and min/max/range queries are not needed.
Common mistakes
- Assuming BST operations are ALWAYS O(log n): Standard BSTs have no self-balancing mechanism. Unbalanced insertion of sorted data creates a spindly tree with O(n) performance.
- Thinking insertion can reorder existing nodes: Standard BST insertion never shifts or modifies existing tree nodes; it simply attaches a new leaf at the unique empty child slot.
- Unclear duplicate handling: Failing to define how duplicates are handled. Standard practice either rejects duplicates or consistently routes them to the right subtree.
Recall questions
- What is the core ordering invariant of a Binary Search Tree?
- What is the worst-case time complexity of searching a non-balancing BST, and when does it occur?
- Where does a new key land during a standard BST insertion?
Questions & answers
Search in a Binary Search Tree: Given the root of a BST and a target integer val, return the node with that value.
Compare target with current node value. If target < node.val recurse left; if target > node.val recurse right; if equal return node.
Approach: BST search path using ordering invariant.
Insert into a Binary Search Tree: Insert a value into a BST and return the root.
Traverse to the correct null child slot, instantiate a new TreeNode(val), attach it to the parent, and return root.
Approach: Recursive or iterative BST search down to a null child reference.
Interesting facts
- Even though simple BSTs can degrade to O(n), randomly built BSTs (inserting keys in random permutation) have an expected height of ~2.99 log2(n), making them balanced on average!
Continue learning
Previous: Binary Search
Previous: Binary tree & traversals
Next: Validate a BST
Next: Lowest common ancestor
Related: Binary Search
Related: Binary tree & traversals
Related: Validate a BST
Related: Lowest common ancestor