Trees

Binary Search Trees

Exploit the BST ordering invariant for search, validation and k-th smallest.

Medium, about 75 minutes to practise.

1Understand

The idea

In a binary search tree every node is greater than everything in its left subtree and smaller than everything in its right subtree. So a search can follow one path from the root (O(h)), and an in-order traversal visits values in sorted order. Validating means checking that range for every node, not just its children.

Intuition

In a BST every node is greater than everything in its left subtree and smaller than everything in its right. A search therefore follows one path from the root, O(h), not O(n).

In-order traversal visits values in sorted order. Validating a BST means checking the allowed range for every node (low, high), not only comparing each node to its immediate children, a classic trap.

Insert and delete maintain the same ordering invariant; balanced BSTs keep h = O(log n), skewed trees degrade to O(n).

What you will be able to do

  • Pass bounds down the recursion
  • Use in-order traversal for sorted order

When to use it

  • Input is a BST
  • Validate BST
  • K-th smallest, in-order successor

2See it

Walkthrough

BST search

Inorder values [1, 2, 3, 4, 5], target = 4, go left/right by comparison.

1 / 5

M
1
2
3
4
5
01234
M → index 2

Root 3. Target 4 > 3 → entire left subtree (<3) is ruled out.

if target < node.val: left else right

Live template

Line 1 active

1def valid(node, lo, hi):
2 if not node: return True
3 if not lo < node.val < hi: return False
4 return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)

Complexity: time O(h) to O(n), space O(h)

Search/insert expected O(h). Validation is O(n). Space O(h) recursion. If you only compare to children, you accept illegal trees, always thread the range or use in-order.

Read the walkthrough as text

Validate BST. Tree: 5 with left 1, right 8 with left 6 and right 9, valid. If 6 were 4, children of 5 still look fine locally but 4 is not > 5.

  1. Call ok(node, lo, hi) with open bounds.
  2. At 5, check lo < 5 < hi, then left with hi=5, right with lo=5.
  3. At 6, require 5 < 6 < 8. A 4 would fail > 5.

In-order and checking non-decreasing values is an equivalent approach.

3Recognise it

Kinds of problems (8)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Search / insert / delete

    Example. Design a BST that supports search, insert and delete.

    How. Compare at each node and recurse left or right; delete uses successor for two children.

  • Validate a BST

    Example. Return false if any node breaks the global BST order.

    How. Pass (lo, hi) bounds down the recursion; node.val must stay strictly inside.

  • K-th smallest (in-order)

    Example. K-th smallest value in a BST.

    How. In-order traversal with a counter; stop at the k-th visited node.

  • LCA in a BST

    Example. Lowest common ancestor when both keys exist in the BST.

    How. Walk from root: split when one key is left and one is right, that node is the LCA.

  • Build a balanced BST from sorted data

    Example. Construct a height-balanced BST from a sorted array.

    How. Recursively pick mid as root; left half builds left subtree, right half the right.

  • BST iterator (in-order with an explicit stack)

    Example. Iterator with next() and hasNext() in O(h) amortised.

    How. Push left spine to stack; next pops, then push left chain of right child.

  • Neighbouring or reverse in-order (min gap, greater tree)

    Example. Minimum absolute difference in BST, or replace each value with next greater.

    How. In-order records previous value or propagates running “next” backward through recursion.

  • Trim or restructure by a value range

    Example. Trim nodes outside [low, high] while keeping a valid BST.

    How. Recurse; drop whole subtrees when node.val is outside range; reattach children when inside.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Only checks children

    Why it happens. Checking only parent against children matches how BSTs are drawn locally.

    How it fails. Left child 3 with parent 5 but ancestor 2 on the path, local check passes, global BST rule fails.

    Fix. Pass (lo, hi) open bounds down the recursion; node.val must satisfy lo < val < hi.

  • Ignores ordering

    Why it happens. When search misses, exploring both sides feels thorough.

    How it fails. target = 5 in BST with root 8, you search both subtrees in O(n) instead of going left once.

    Fix. Compare to root: smaller → left only, larger → right only.

  • Delete with two children

    Why it happens. Deleting by linking children directly is the obvious fix.

    How it fails. Remove node with two children without successor, middle order breaks and search returns wrong nodes.

    Fix. Replace with inorder successor (min of right subtree), then delete duplicate leaf.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons