LESSON 17 · PATTERN GUIDE

BST Problems

Use the binary search tree ordering invariant to search, validate, and select values efficiently.

FIRST, LEARN THE PATTERNEvery node's left subtree contains smaller values and its right subtree larger values, subject to the duplicate policy.

The prompt names a binary search tree, asks for kth smallest, nearest common ancestor, or ordered lookup.

How to approach it

Use the ordering rule to choose one subtree at a time; inorder traversal visits values in sorted order.

Watch out for

A plain BST can become a chain and take O(n). Validation needs lower and upper bounds beyond checking parent-child pairs.

A CLOSER EXPLANATION

The BST invariant lets a search discard a subtree: if the target is smaller, everything in the right subtree is too large. Inorder traversal visits values in sorted order, which supports rank queries. Validation must carry bounds inherited from ancestors, not just compare each node with its parent.

NOW YOU TRY

Practice question

What is the third-smallest value in the BST with root 5, left subtree 3(2,4), and right child 8?

EXAMPLEInorder order = [2, 3, 4, 5, 8]Give your answer before revealing the explanation.

Show a hint

Inorder traversal lists BST values from smallest to largest.

Show an answer

CONNECT IT TO REAL LIFE

BST Problems at work

A shop stores product prices in a balanced search tree. How can it find the cheapest product priced at least $50 without scanning every product?

Show one possible approach

Search by price while keeping the smallest qualifying node as a candidate. When a node is below $50 go right; when it qualifies, save it and continue left for a cheaper valid price.

Practice next

Use these problem IDs to find additional practice for this pattern:

9899230235450700