BST
Overview
A Binary Search Tree is a specialized Binary Tree with a strict mathematical rule: For any given node, ALL nodes in its Left subtree must be SMALLER than it, and ALL nodes in its Right subtree must be LARGER than it. This rule unlocks incredible power. Just like looking up a word in a dictionary, a BST allows you to cut your search space in half with every single step, making searching, insertion, and deletion incredibly fast: O(log N) time.
Syntax
By instantly discarding half of the tree at every node, searching a tree with 1 Million nodes only takes around 20 operations. That is the magic of O(log N).
public TreeNode searchBST(TreeNode root, int target) {
// Base case: root is null or we found the target
if (root == null || root.val == target) {
return root;
}
// If target is greater, completely ignore the left side!
if (root.val < target) {
return searchBST(root.right, target);
}
// If target is smaller, completely ignore the right side!
return searchBST(root.left, target);
}Insertion follows the exact same logic. We traverse left or right until we hit a `null` spot, then drop the new node there.
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}Common Pitfalls
- Creating an Unbalanced Tree. If you insert sorted data (1, 2, 3, 4, 5) into a basic BST, it just forms a straight line to the right. It degrades into a Linked List, and search times become a terrible O(N).
- Using == instead of `.compareTo()` when building BSTs that hold Strings or custom Objects.
Interview Tips
- The strict left/right sorting rule of a BST allows for O(log N) search times, acting like a dynamic Binary Search.
Real-World Example
Java's `TreeMap` and `TreeSet` are internally implemented as Red-Black Trees (a self-balancing BST), providing guaranteed O(log N) sorting and retrieval.
public class HighScoreBoard {
// Automatically keeps scores sorted using a BST internally
TreeSet<Integer> scores = new TreeSet<>();
public void addScore(int score) {
scores.add(score);
}
public int getHighestScore() {
return scores.last(); // O(log N) retrieval
}
}