Overview

A binary search tree adds one rule to a binary tree: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. That rule turns every lookup into binary search along a single path, and an inorder traversal visits the values in sorted order.

The catch is shape. A BST built from sorted input degenerates into a linked list with O(n) operations. Self-balancing trees (AVL, red–black) fix this by rotating nodes, and you use them every day without noticing: C++ std::map and std::set and Java's TreeMap are balanced BSTs with guaranteed O(log n) operations.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Search / insert / deleteO(h): O(log n) balanced, O(n) skewed
Inorder traversalO(n)
Min / maxO(h) — walk left or right

Patterns to recognise

Range-bounded recursion

Use it for: Validate BST, trim a BST, range sum of BST.

Pass (low, high) bounds down; prune subtrees outside the range.

Inorder walk

Use it for: k-th smallest, recover swapped nodes, BST iterator.

Use the sorted order directly, iteratively with a stack if needed.

Guided descent

Use it for: Search, insert, LCA in a BST, closest value.

One comparison per level decides the direction.

Code template

Validate a BST with bounds
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

Common mistakes

  • Only comparing a node with its children misses violations deeper down.
  • Using INT_MIN/INT_MAX as bounds breaks when node values equal them — use wider types or nullable bounds.
  • Check whether duplicates are allowed and on which side they go.

Quick check

Three questions on BST. Get all three right to earn +15 XP.

  1. An inorder traversal of a binary search tree produces values in:

  2. Searching a balanced BST costs O(log n). What is the worst case for an unbalanced one?

  3. Why is "left child < node < right child" not enough to validate a BST?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on BST?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor