DSA Series · Trees
· Part 3
Binary Search Trees (BST)
The BST Property
A BST enforces an ordering invariant: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This enables O(log n) search, insert, and delete on balanced trees.
BST Search
function search(node, key):
if node == null: return null if key == node.val: return node if key < node.val: return search(node.left, key) return search(node.right, key)
if node == null: return null if key == node.val: return node if key < node.val: return search(node.left, key) return search(node.right, key)
Complexity: O(h) where h = height. For a balanced tree h = log n. For a skewed tree h = n.
▶ BST Search Animation
Watch how BST search navigates left or right at each node by comparing values.
BST Insertion
▶ BST Insertion Animation
Watch how value 13 finds its position by comparing at each level.
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insert(root->left, val);
else if (val > root->val)
root->right = insert(root->right, val);
return root;
}BST Deletion
Three cases when deleting a node:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
if (!root->left) return root->right;
if (!root->right) return root->left;
TreeNode* successor = root->right;
while (successor->left) successor = successor->left;
root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}
return root;
}▶ BST Deletion Animation
See how each deletion case works. The tree resets each time.
Summary
- BST ordering: left < root < right, recursively.
- Search, insert, and delete are all O(h) where h is the tree height.
- Deletion has three cases: leaf, one child, and two children (replace with in-order successor).
- Worst case O(n) when the tree degenerates to a linked list.