A Binary Search Tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This one rule gives us the power of binary search on a tree structure.
Why does this matter? Because searching, inserting, and deleting all become O(log n) on average. That’s the same speed as binary search on a sorted array, but with the flexibility to insert and delete without shifting elements.
The BST Property
The key insight: an inorder traversal of a BST gives us elements in sorted order. This is how many BST problems are solved.
Search in a BST
Searching is elegant. Compare the target with the current node. If it’s smaller, go left. If it’s larger, go right. If it matches, we found it.
function searchBST(node, target) {
if (!node) return null; // not found
if (target === node.val) return node; // found it
if (target < node.val)
return searchBST(node.left, target); // go left
return searchBST(node.right, target); // go right
}def search_bst(node, target):
if not node: return None # not found
if target == node.val: return node # found it
if target < node.val:
return search_bst(node.left, target) # go left
return search_bst(node.right, target) # go rightTreeNode searchBST(TreeNode node, int target) {
if (node == null) return null; // not found
if (target == node.val) return node; // found it
if (target < node.val)
return searchBST(node.left, target); // go left
return searchBST(node.right, target); // go right
}Time: O(h) where h is the height. For a balanced tree that’s O(log n). For a skewed tree, it degrades to O(n).
Insert into a BST
Inserting follows the same logic as search. We walk down the tree until we find an empty spot, then place the new node there.
function insertBST(node, val) {
if (!node) return new TreeNode(val); // found empty spot
if (val < node.val)
node.left = insertBST(node.left, val); // go left
else
node.right = insertBST(node.right, val); // go right
return node;
}def insert_bst(node, val):
if not node: return TreeNode(val) # found empty spot
if val < node.val:
node.left = insert_bst(node.left, val) # go left
else:
node.right = insert_bst(node.right, val) # go right
return nodeTreeNode insertBST(TreeNode node, int val) {
if (node == null) return new TreeNode(val); // found empty spot
if (val < node.val)
node.left = insertBST(node.left, val); // go left
else
node.right = insertBST(node.right, val); // go right
return node;
}Time: O(h) — same as search.
Delete from a BST
Deletion is the trickiest operation. There are three cases:
- Node is a leaf (no children) — just remove it.
- Node has one child — replace the node with its child.
- Node has two children — find the inorder successor (smallest node in right subtree), copy its value to the current node, then delete the successor.
function deleteBST(node, val) {
if (!node) return null;
if (val < node.val) node.left = deleteBST(node.left, val);
else if (val > node.val) node.right = deleteBST(node.right, val);
else {
if (!node.left) return node.right; // case 1 & 2
if (!node.right) return node.left; // case 2
// case 3: find inorder successor
let succ = node.right;
while (succ.left) succ = succ.left;
node.val = succ.val;
node.right = deleteBST(node.right, succ.val);
}
return node;
}def delete_bst(node, val):
if not node: return None
if val < node.val: node.left = delete_bst(node.left, val)
elif val > node.val: node.right = delete_bst(node.right, val)
else:
if not node.left: return node.right # case 1 & 2
if not node.right: return node.left # case 2
# case 3: find inorder successor
succ = node.right
while succ.left: succ = succ.left
node.val = succ.val
node.right = delete_bst(node.right, succ.val)
return nodeTreeNode deleteBST(TreeNode node, int val) {
if (node == null) return null;
if (val < node.val) node.left = deleteBST(node.left, val);
else if (val > node.val) node.right = deleteBST(node.right, val);
else {
if (node.left == null) return node.right; // case 1 & 2
if (node.right == null) return node.left; // case 2
// case 3: find inorder successor
TreeNode succ = node.right;
while (succ.left != null) succ = succ.left;
node.val = succ.val;
node.right = deleteBST(node.right, succ.val);
}
return node;
}Validate a BST
A common interview problem. The trick is that we can’t just check left < node < right locally — we need to track the valid range for each node.
For example, in the invalid BST above, 12 is correctly to the right of 3, but it violates the rule that everything in the left subtree of 8 must be less than 8.
function isValidBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) // left must be < node
&& isValidBST(node.right, node.val, max); // right must be > node
}def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
if not node: return True
if node.val <= lo or node.val >= hi: return False
return (is_valid_bst(node.left, lo, node.val) # left must be < node
and is_valid_bst(node.right, node.val, hi)) # right must be > nodeboolean isValidBST(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) // left must be < node
&& isValidBST(node.right, node.val, max); // right must be > node
}
// Call: isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)Time: O(n) — we check every node. Space: O(h).
Kth Smallest Element
Since inorder traversal gives us sorted order, the kth smallest is just the kth element in an inorder traversal. We can stop early once we’ve counted k nodes.
function kthSmallest(root, k) {
let count = 0, result = null;
function inorder(node) {
if (!node || result !== null) return;
inorder(node.left);
count++;
if (count === k) { result = node.val; return; }
inorder(node.right);
}
inorder(root);
return result;
}def kth_smallest(root, k):
count, result = [0], [None] # use lists to mutate in closure
def inorder(node):
if not node or result[0] is not None: return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]int kthSmallest(TreeNode root, int k) {
int[] state = {k, 0}; // [remaining count, result]
inorderK(root, state);
return state[1];
}
void inorderK(TreeNode node, int[] state) {
if (node == null) return;
inorderK(node.left, state);
state[0]--;
if (state[0] == 0) { state[1] = node.val; return; }
inorderK(node.right, state);
}Time: O(h + k) — we go down to the leftmost node then visit k nodes. Space: O(h).
BST Complexity Summary
| Operation | Average | Worst (Skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
The worst case happens when the tree becomes a straight line (like inserting sorted data). Self-balancing trees (AVL, Red-Black) fix this by ensuring the height stays O(log n), but those are rarely asked in interviews.
Key Takeaways
- The BST property (left < node < right) gives us O(log n) operations on average.
- Inorder traversal of a BST = sorted order. This is the most important thing to remember.
- Deletion has three cases. The two-children case uses the inorder successor.
- Validating a BST requires tracking min/max bounds, not just comparing parent and child.
In simple language, a BST is like a sorted array that we can insert into and delete from efficiently. The tradeoff is that it can become unbalanced, but for interview purposes, we usually assume reasonable balance.