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
| Operation | Cost |
|---|---|
| Search / insert / delete | O(h): O(log n) balanced, O(n) skewed |
| Inorder traversal | O(n) |
| Min / max | O(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
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))
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int v = 0) : val(v), left(nullptr), right(nullptr) {}
};
bool isValidBST(TreeNode* root, long long low = LLONG_MIN, long long high = LLONG_MAX) {
if (!root) return true;
if (root->val <= low || root->val >= high) return false;
return isValidBST(root->left, low, root->val) &&
isValidBST(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.
-
An inorder traversal of a binary search tree produces values in:
Everything in the left subtree is smaller and everything in the right is larger.
-
Searching a balanced BST costs O(log n). What is the worst case for an unbalanced one?
Inserting sorted values produces a chain that behaves like a linked list.
-
Why is "left child < node < right child" not enough to validate a BST?
Pass a (low, high) range down the tree, or check that the inorder sequence is strictly increasing.
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.
- Search in a Binary Search TreeLeetCode Easy +20
- Convert Sorted Array to Binary Search TreeLeetCode Easy +20
- Validate Binary Search TreeLeetCode Medium +40
- Kth Smallest Element in a BSTLeetCode Medium +40
- Lowest Common Ancestor of a Binary Search TreeLeetCode Medium +40
- Insert into a Binary Search TreeLeetCode Medium +40
- Delete Node in a BSTLeetCode Medium +40
- Recover Binary Search TreeLeetCode Medium +40
Stuck on BST?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor