BST Visualization for Coding Interviews
Insert/search/delete with unbalanced worst-case demo.
Concept
A Binary Search Tree is the simplest data structure that keeps keys in sorted order while still supporting dynamic insertion and deletion. Every node stores a key and two children, with the invariant that every key in the left subtree is strictly less than the node's key and every key in the right subtree is strictly greater. That single invariant turns a tree walk into an ordered traversal and turns a search into a series of greater-than comparisons that slice the candidate set in half at each step - as long as the tree stays reasonably balanced. BSTs are the conceptual base class behind AVL trees, red-black trees, order statistic trees, and interval trees, and understanding the plain BST in detail is the shortest path to understanding those balanced variants. The one caveat is worst-case behavior: a BST built from a sorted input degenerates into a linked list, which is why production code almost always uses a self-balancing variant.
How it works
Search walks from the root, comparing the query to the current node's key. If they match you return the node; if the query is smaller you go left; otherwise right. You stop when you hit null. Insert follows the same walk, but when it hits null it replaces that null child with a fresh node, which is why insertion cost matches search cost. Delete is the one nontrivial operation because the BST invariant has to survive the removal. Three cases: a leaf node is simply detached from its parent; a node with one child is spliced out and the surviving child is hooked onto the parent; a node with two children is replaced by its in-order successor - the leftmost node of its right subtree - whose key is copied up and whose own node is then deleted (which falls into one of the first two cases, because an in-order successor cannot have a left child). In-order traversal visits keys in sorted order in O(n) time, which is a consequence of the invariant and is the foundation of algorithms like BST-to-sorted-array and k-th smallest element. All three operations cost O(h) where h is the height of the tree, which is O(log n) on a balanced BST and O(n) on a degenerate one.
Implementation
public class BST {
static class BSTNode {
int key;
BSTNode left, right;
BSTNode(int key) { this.key = key; }
}
private BSTNode root;
public void insert(int key) { root = insert(root, key); }
private BSTNode insert(BSTNode node, int key) {
if (node == null) return new BSTNode(key);
if (key < node.key) node.left = insert(node.left, key);
else if (key > node.key) node.right = insert(node.right, key);
return node; // duplicate ignored
}
public boolean contains(int key) { return search(root, key) != null; }
private BSTNode search(BSTNode node, int key) {
if (node == null || node.key == key) return node;
return key < node.key ? search(node.left, key) : search(node.right, key);
}
public void delete(int key) { root = delete(root, key); }
private BSTNode delete(BSTNode node, int key) {
if (node == null) return null;
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else {
// found node to remove
if (node.left == null) return node.right;
if (node.right == null) return node.left;
BSTNode successor = minNode(node.right); // in-order successor
node.key = successor.key;
node.right = delete(node.right, successor.key);
}
return node;
}
private BSTNode minNode(BSTNode node) {
while (node.left != null) node = node.left;
return node;
}
/** In-order traversal yields keys in sorted order. */
public void inorder(BSTNode node, java.util.List<Integer> out) {
if (node == null) return;
inorder(node.left, out);
out.add(node.key);
inorder(node.right, out);
}
}Complexity
- Search:
O(log n) balanced, O(n) worst-case - Insert:
O(log n) balanced, O(n) worst-case - Delete:
O(log n) balanced, O(n) worst-case - Space:
O(n)
Common pitfalls
- Building a BST from already-sorted input produces a degenerate O(n) linked list; shuffle or use a balanced variant.
- Deleting a two-child node by splicing rather than using the in-order successor silently violates the BST invariant.
- Treating duplicate keys inconsistently - pick one policy (ignore, go-left, or store a count) and stick with it.
- Using reference equality when comparing node keys instead of key-based comparators for non-primitive types.
- Returning the successor's node instead of copying its key, leaving dangling parent pointers in languages with explicit parent links.
Key design decisions & trade-offs
- Balancing strategy — Chosen: No auto-balance in a plain BST. Simpler to implement and teach; acceptable when input order is random. Production code should upgrade to AVL or red-black to bound worst-case height.
- Delete strategy — Chosen: In-order successor replacement. Always a node with at most one child, so the recursive delete terminates cleanly. Using the predecessor is symmetric and equally valid.
- Duplicate handling — Chosen: Ignore duplicates on insert. Keeps the invariant strict (<, >) and makes search unambiguous. A multiset variant would store a count field on the node instead.
Practice problems
Interview follow-ups
- Upgrade the plain BST to a self-balancing AVL tree with rotations.
- Add an order statistic field (subtree size) to support O(log n) k-th smallest.
- Implement an iterator that yields keys in sorted order using an explicit stack.
- Support range queries: collect all keys in [lo, hi] in O(log n + k).
- Convert a sorted array into a balanced BST in O(n) by building bottom-up.
Why it matters
BST is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".