Binary Search Trees — Operations, Balancing, and Interview Questions
The Interview Question
Explain the operations on a binary search tree. What's the problem with unbalanced BSTs and how is it solved?
Expert Answer
A BST is a binary tree where each node's left subtree contains only values less than the node, and the right subtree contains only values greater. This property enables binary search: at each node, you eliminate half the remaining tree. Search, insert, and delete are all O(h) where h is the height. In a balanced tree, h = log(n), giving O(log n) operations. The problem: if you insert sorted data (1, 2, 3, 4, 5), the BST degenerates into a linked list with h = n, making all operations O(n). Self-balancing BSTs solve this. AVL trees maintain a strict balance — the height difference between left and right subtrees is at most 1, enforced through rotations after every insert/delete. Red-Black trees are less strict (roughly balanced) but require fewer rotations on average, making inserts faster. In practice, Red-Black trees are used more often (Java TreeMap, C++ std::map) because the insert performance matters more than the slightly better search of AVL trees.
Key Points to Hit in Your Answer
- BST property: left < node < right (for all subtrees)
- Balanced BST: O(log n) search, insert, delete; Unbalanced: O(n)
- In-order traversal of BST produces sorted output
- Delete has three cases: leaf, one child, two children (replace with in-order successor)
- AVL: stricter balance = faster search, more rotations
- Red-Black: looser balance = faster inserts, fewer rotations
- B-trees used in databases — optimized for disk reads with high branching factor
Code Example
// BST insert and search
class BSTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function insert(root, value) {
if (!root) return new BSTNode(value);
if (value < root.value) root.left = insert(root.left, value);
else if (value > root.value) root.right = insert(root.right, value);
return root;
}
function search(root, value) {
if (!root) return false;
if (value === root.value) return true;
if (value < root.value) return search(root.left, value);
return search(root.right, value);
}
// In-order traversal → sorted output
function inOrder(root) {
if (!root) return [];
return [...inOrder(root.left), root.value, ...inOrder(root.right)];
}What Interviewers Are Really Looking For
Know all three deletion cases cold — especially two-children deletion with in-order successor. Be able to explain why sorted input is worst-case for BST and how rotations restore balance. Follow-up questions often involve: 'Find the kth smallest element in a BST' (in-order traversal) or 'Validate if a tree is a valid BST' (pass min/max bounds recursively).
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →