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.

🔍
The dictionary analogy
Open a dictionary to the middle — is your word before or after?

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

20 10 30 5 15 25 35 3 Inorder: 3 → 5 → 10 → 15 → 20 → 25 → 30 → 35 (sorted!)

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.

BST property vs. just the immediate children:
A common mistake is checking only that 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.

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.

bst_insert.py O(log n) average, O(n) worst
Output
After inserting 12: [5, 10, 12, 15, 20, 25, 30, 35]

Walk-through: inserting 12

  1. Root (20): 12 < 20, go left.
  2. Node 10: 12 > 10, go right.
  3. Node 15: 12 < 15, go left.
  4. None: Empty spot found — create TreeNode(12) here.
Why return root?
The recursive approach reassigns 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:

🗑️
Three deletion cases
Leaf, one child, or two children
  • 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)

Before 10 5 15 3 → After 15 5 3
Node being deleted Remaining nodes
bst_delete.py O(log n) average, O(n) worst
Output
After deleting 10: [3, 5, 15, 20, 25, 30, 35]
Why the inorder successor?
The inorder successor is the smallest value in the right subtree — it's guaranteed to be greater than everything in the left subtree and less than everything else in the right subtree. Swapping it in preserves the BST property perfectly.

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)

Balanced — O(log n) 4 2 6 1 3 5 Height = 2, 5 nodes Degenerate — O(n) 1 2 3 4 5
Inserting 1, 2, 3, 4, 5 in order creates the degenerate case — every node only has a right child.

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.

Interview tip:
When analyzing BST time complexity, always state both the average case (O(log n) for balanced) and the worst case (O(n) for degenerate). Interviewers will probe whether you know the difference.

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).

validate_bst.py O(n) time, O(h) space
Output
Valid BST: True Invalid BST: False

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.

Alternative approach — inorder traversal:
Since inorder traversal of a valid BST produces sorted values, you can do an inorder walk and check that each value is strictly greater than the previous. Both approaches are O(n) time, but the min/max bounds approach is more elegant in interviews.

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.

kth_smallest.py O(H + k) time, O(H) space
Output
1st smallest: 3 3rd smallest: 10 5th smallest: 20

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.

Why iterative over recursive?
The iterative version lets us early-exit cleanly. A recursive inorder traversal would require extra bookkeeping (a nonlocal counter or passing state through returns) to stop mid-traversal. Interviewers appreciate the stack-based approach for its clarity.

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.

lca_bst.py O(log n) average, O(n) worst
Output
LCA of 3 and 15: 10 LCA of 5 and 35: 20 LCA of 25 and 35: 30

Walk-through: LCA of 3 and 15

  1. Root (20): Both 3 < 20 and 15 < 20, go left.
  2. Node 10: 3 < 10 but 15 > 10 — they diverge! Node 10 is the LCA.
BST LCA vs. general binary tree LCA:
For a generic binary tree (LeetCode 236), you need to search both subtrees and check if each contains p or q — O(n) always. For a BST, you can navigate directly using the ordering property — O(log n) on average. Always clarify with your interviewer whether the tree is a BST.

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

BST Iterator (LeetCode 173)
Your task:

Implement a BSTIterator class that takes a BST root and supports two operations:

  • next() — returns the next smallest number in the BST.
  • has_next() — returns True if 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.

Use a stack to simulate iterative inorder traversal. In __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

Question 1 of 5
What order does an inorder traversal of a valid BST produce?
Question 2 of 5
When deleting a node with two children from a BST, what value replaces it?
Question 3 of 5
What causes a BST to degenerate into O(n) operations?
Question 4 of 5
In the validate BST problem, why can't you just check that each node's value is between its immediate children?
Question 5 of 5
How does finding the lowest common ancestor in a BST differ from a generic binary tree?
0
/5
Great work! You've mastered BST fundamentals.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →