Binary Search Trees

Intermediate · 16 min read · Problem-Solving Patterns, Trees

In-order is sorted: validation, k-th smallest and searching with bounds.

A binary search tree is a binary tree with one promise: everything in a node's left subtree is smaller, everything in its right subtree is larger. That single rule gives you two superpowers. You can search by going left or right, like binary search, in O(height).

Fact 1: in-order is sorted

In-order (left, node, right) visits 1, 3, 4, 6, 7, 8, 10, 14 — sorted. So "the k-th smallest" is "the k-th node an in-order traversal visits", and you can stop as soon as you reach it:

Fact 2: search by going left or right

Both are O(h): O(log n) when the tree is balanced, O(n) when it degenerates into a line (e.g. inserting sorted values). That's why real libraries use self-balancing trees (Java's TreeMap is a red-black tree).

Worked problems

The classic mistake is checking only left.val < node.val < right.val. That misses a deeper node violating an ancestor:

BST operations at a glance

In Java, a TreeMap/TreeSet is a balanced BST you can use directly: floorKey, ceilingKey, headMap, firstKey are all O(log n).

Practice ladder

Interview questions

  • Why isn't it enough to check that each node is greater than its left child and smaller than its right child?
  • What is the complexity of BST operations, and when does it degrade?

Further reading

Key takeaways

  • A BST orders every subtree: left smaller, right larger.
  • In-order traversal is sorted → k-th smallest, iterators, validation, recovering swapped nodes.
  • Search, insert, delete, LCA and closest value walk one path: O(h), which is only O(log n) if balanced.
  • Validate with (lo, hi) ranges passed down from ancestors, using long bounds.
  • In Java, TreeMap/TreeSet give you a balanced BST for free.

Previous: Tree BFS: Level by Level · Next: Graphs & Grids: BFS and DFS