The BST Property
A Binary Search Tree is a binary tree where every node satisfies one rule: all values in the left subtree are less than the node, and all values in the right subtree are greater than the node. This holds for every node, not just the root.
Looking up a word in a physical dictionary is exactly how BST search works. You open to the middle, check if your word comes before or after, then repeat on the correct half. Each comparison eliminates half the remaining pages. That's O(log n) — the same efficiency a BST gives you.
A Valid BST — Inorder Traversal Gives Sorted Order
Key insight: An inorder traversal (left → root → right) of a BST always produces values in sorted ascending order. This is a direct consequence of the BST property and is frequently used in interview problems.
left.val < root.val < right.val. That's necessary but not sufficient. The BST property requires all values in the left subtree to be less, and all in the right to be greater. We'll see this pitfall in the "Validate BST" problem below.
Search in a BST
Searching a BST is elegant: compare the target with the current node and go left or right. Each comparison eliminates one subtree, halving the search space — just like binary search on a sorted array.
Walk-through: searching for 15
- Start at root (20): 15 < 20, go left.
- Node 10: 15 > 10, go right.
- Node 15: 15 == 15, found it!
Only 3 comparisons for an 8-node tree. In a balanced BST with n nodes, the height is O(log n), so search takes O(log n) time.
Insert into a BST
Insertion follows the same path as search: navigate left or right until you find an empty spot (a None child), then place the new node there. The new node is always inserted as a leaf.
Walk-through: inserting 12
- Root (20): 12 < 20, go left.
- Node 10: 12 > 10, go right.
- Node 15: 12 < 15, go left.
- None: Empty spot found — create
TreeNode(12)here.
root.left or root.right at each level. For the top-level caller, returning root ensures you get back the (unchanged) root of the entire tree. If the tree was empty (root is None), the new node becomes the root.
Delete from a BST
Deletion is the trickiest BST operation because removing a node must preserve the BST property. There are three cases to handle:
- Case 1 — Leaf node: Simply remove it. No children to worry about.
- Case 2 — One child: Replace the node with its only child. The child slides up.
- Case 3 — Two children: Find the inorder successor (smallest node in the right subtree). Copy its value to the current node, then delete the successor (which has at most one child).
Deleting Node 10 (Two Children) — Replace with Inorder Successor (15)
Balanced vs. Unbalanced BSTs
The efficiency of a BST depends entirely on its shape. A balanced BST has height O(log n), giving O(log n) operations. An unbalanced BST can degenerate into a linked list with O(n) height.
Balanced (height 2) vs. Degenerate (height 4)
When does a BST degenerate?
- Sorted input: Inserting values in ascending (or descending) order creates a straight line.
- Nearly sorted input: Still produces a heavily skewed tree.
Self-balancing trees like AVL trees and Red-Black trees solve this by rebalancing after every insertion/deletion, guaranteeing O(log n) height. Python's sortedcontainers library uses a B-tree variant. In interviews, you're usually expected to know that vanilla BSTs can degenerate, and that balanced variants exist.
Problem: Validate BST
Given a binary tree, determine if it's a valid BST. This is LeetCode 98 and one of the most frequently asked tree interview problems.
Approach: Pass min/max bounds down the tree. Every node's value must be within its allowed range. The root can be anything. A left child must be less than its parent (new upper bound). A right child must be greater (new lower bound).
Why not just check immediate children?
In the invalid tree above, node 25 is the right child of node 10, so 25 > 10 looks fine locally. But 25 is in the left subtree of root 20, and all left-subtree values must be < 20. The min/max bounds approach catches this: when we go left from 20, we set hi=20, so 25 fails the root.val >= hi check.
Problem: Kth Smallest Element
Given a BST and an integer k, return the kth smallest element. This is LeetCode 230.
Key insight: Inorder traversal visits BST nodes in ascending order. So the kth node visited during inorder traversal is the kth smallest element. We don't need to traverse the entire tree — stop as soon as we've visited k nodes.
The iterative approach uses a stack to simulate the inorder traversal. We push nodes going left, pop them one at a time (processing in sorted order), and move right. We stop the moment we've processed the kth node — no need to visit the rest.
Problem: Lowest Common Ancestor in BST
Given a BST and two nodes p and q, find their lowest common ancestor (LCA). This is LeetCode 235.
Key insight: The BST property makes this much easier than LCA in a generic binary tree. If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, it's in the right subtree. Otherwise, the current node is the LCA — it's the split point where p and q diverge.
Walk-through: LCA of 3 and 15
- Root (20): Both 3 < 20 and 15 < 20, go left.
- Node 10: 3 < 10 but 15 > 10 — they diverge! Node 10 is the LCA.
Try It Yourself
Validate a Binary Search Tree
Given a binary tree, write a function to check if it is a valid BST using the min/max bounds approach.
Challenge
Implement a BSTIterator class that takes a BST root and supports two operations:
next()— returns the next smallest number in the BST.has_next()— returnsTrueif there are more elements to iterate.
Both operations must run in O(1) average time and use O(h) space where h is the tree height. You cannot flatten the entire tree into a list upfront (that's O(n) space).
Example: For the BST [7, 3, 15, None, None, 9, 20], calling next() repeatedly should yield 3, 7, 9, 15, 20.
__init__, push all left children of root onto the stack. In next(), pop the top node (smallest), then push all left children of its right child. The stack always holds the "leftmost path" of the unvisited portion. has_next() simply checks if the stack is non-empty. This gives O(h) space and O(1) amortized time per next() call.Quiz
You've learned to search in O(log n).
Now find your career in record time.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →