Algorithms - 13. Binary Search Tree (BST)
When to use Binary Search Trees
Use Binary Search Trees when you need to maintain a dynamically changing sorted collection with efficient operations. While most commonly used for searching sorted data, BSTs can be adapted for:
- Database indexing (classic use case) - B-trees and B+ trees are BST variants
- Priority queues with frequent updates (when heap operations aren't sufficient)
- Range queries - finding all values within a given range
- Order statistics - finding the kth smallest/largest element
- Autocomplete systems - prefix matching with lexicographic ordering
- File systems - directory structures and file organization
- Any problem requiring maintaining sorted order with frequent insertions/deletions
Example problem
Music Playlist Manager: You're building a music player that maintains a playlist sorted by song title. Given operations like adding songs ["Bohemian Rhapsody", "Imagine", "Hey Jude", "Let It Be", "Yesterday", "Come Together"], efficiently:
- Add new songs while maintaining alphabetical order
- Search for specific songs to play them
- Delete songs from the playlist
- Find all songs starting with a given letter or prefix
After processing all operations:
- The BST maintains songs in alphabetical order
- Search for "Hey Jude" takes O(log n) average time
- We can get all songs in sorted order with an inorder traversal
- Range queries like "all songs starting with 'H'" are efficient
Answer: BST automatically maintains sorted order, making all these operations efficient without manual sorting.
What Binary Search Tree Actually Does
A Binary Search Tree is a hierarchical data structure that maintains elements in sorted order through a simple rule. It provides three core operations:
- SEARCH: Find if an element exists in the tree
- INSERT: Add a new element while maintaining BST property
- DELETE: Remove an element and reorganize the tree
Think of it like organizing a library's card catalog:
- SEARCH: "Do we have this book?"
- INSERT: "Add this new book's card in the right alphabetical position"
- DELETE: "Remove this book's card and reorganize if needed"
How the Operations Work
SEARCH Operation - "Is this value in the tree?"
When you call search(root, 42), it:
- Starts at the root node
- Compares 42 with current node's value
- Goes left if 42 is smaller, right if larger
- Returns true if found, false if reaches null
- Key efficiency: Eliminates half the remaining tree at each step
INSERT Operation - "Add this value maintaining order"
When you call insert(root, 35), it:
- Searches for where 35 should be (like search operation)
- Creates a new node when it reaches a null position
- Attaches the new node as a left or right child
- BST property maintained: All values in left subtree < node < all values in right subtree
DELETE Operation - "Remove this value and reorganize"
When you call delete(root, 50), it handles three cases:
- Leaf node: Simply remove it
- One child: Replace node with its child
- Two children: Find inorder successor (smallest in right subtree), replace value, delete successor
When These Operations Happen
These operations only happen when you explicitly call them:
const bst = new BinarySearchTree();
// INSERT: Explicitly add elements
bst.insert(50); // Creates root
bst.insert(30); // Goes left of 50
bst.insert(70); // Goes right of 50
bst.insert(40); // Goes right of 30
// SEARCH: Check if element exists
let found = bst.search(40); // Returns true
let notFound = bst.search(25); // Returns false
// DELETE: Remove element
bst.delete(30); // Removes 30, reorganizes treeThe beauty of BST is that it maintains sorted order automatically - you never need to manually sort or reorganize the data!
Single most important insight
The BST property (left < parent < right) at every node creates a decision tree for searching - and by consistently following "go left for smaller, right for larger," we eliminate half the search space at each step, achieving O(log n) search in balanced trees.
Mental note: The algorithm's genius lies in encoding sorted order into the tree structure itself. At each node, we only need to make one decision: go left or right based on comparison. This simple binary decision at each level automatically maintains sorted data and enables binary search without arrays.
Decision Framework
BST operations involve these key decisions:
During Search:
- Is current node null? Return not found
- Is target equal to current value? Return found
- Is target less than current? Go left
- Is target greater than current? Go right
During Insert:
- Follow search path until reaching null
- Create new node at the null position
- Attach as left child if value is less than parent
- Attach as right child if value is greater than parent
During Delete (most complex):
- No children (leaf)? Simply remove
- One child? Replace with that child
- Two children? Find inorder successor, swap values, delete successor
Why BST Property Matters
The BST property ensures all operations can ignore entire subtrees:
Without BST Property (Unsorted Tree):
To find value 35:
50
/ \
70 30
/ \ / \
20 40 60 10
Must check ALL 7 nodes - O(n) time!With BST Property:
To find value 35:
50
/ \
30 70 ← Ignore entire right subtree!
/ \
20 40 ← Only check left of 30, ignore 20!
Path: 50 → 30 → 40 → not found (only 3 checks)The BST property guarantees:
- All values in left subtree < node value
- All values in right subtree > node value
- This applies recursively to every subtree
- Result: We can eliminate ~50% of remaining nodes at each step
This is why balanced BSTs achieve O(log n) operations - the height determines the maximum number of comparisons needed!
Code
// Node structure for the tree
class TreeNode {
constructor(value) {
this.value = value;
this.left = null; // Left child (smaller values)
this.right = null; // Right child (larger values)
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// SEARCH: Find if a value exists in the tree
search(targetValue) {
return this.searchFromNode(this.root, targetValue);
}
searchFromNode(currentNode, targetValue) {
// Base case: reached end of path
const reachedEndOfPath = currentNode === null;
if (reachedEndOfPath) {
return false; // Value not found
}
// Extract current node's value for comparison
const currentValue = currentNode.value;
// DECISION FRAMEWORK: Three-way comparison
const foundTarget = targetValue === currentValue;
const shouldSearchLeft = targetValue < currentValue;
const shouldSearchRight = targetValue > currentValue;
if (foundTarget) {
return true; // Successfully found the target!
}
if (shouldSearchLeft) {
// Target is smaller - search left subtree only
const leftSubtree = currentNode.left;
return this.searchFromNode(leftSubtree, targetValue);
}
if (shouldSearchRight) {
// Target is larger - search right subtree only
const rightSubtree = currentNode.right;
return this.searchFromNode(rightSubtree, targetValue);
}
}
// INSERT: Add a new value maintaining BST property
insert(newValue) {
// Start insertion from root, update root if needed
this.root = this.insertIntoSubtree(this.root, newValue);
}
insertIntoSubtree(currentNode, newValue) {
// Base case: found empty spot for new node
const foundEmptySpot = currentNode === null;
if (foundEmptySpot) {
const newNode = new TreeNode(newValue);
return newNode;
}
// Extract current value for comparison
const currentValue = currentNode.value;
// DECISION FRAMEWORK: Determine insertion direction
const insertToLeft = newValue < currentValue;
const insertToRight = newValue > currentValue;
const isDuplicate = newValue === currentValue;
if (insertToLeft) {
// New value is smaller - insert in left subtree
const updatedLeftSubtree = this.insertIntoSubtree(
currentNode.left,
newValue
);
currentNode.left = updatedLeftSubtree;
} else if (insertToRight) {
// New value is larger - insert in right subtree
const updatedRightSubtree = this.insertIntoSubtree(
currentNode.right,
newValue
);
currentNode.right = updatedRightSubtree;
} else if (isDuplicate) {
// Value already exists - skip insertion (no duplicates allowed)
// Do nothing, just return the unchanged node
}
return currentNode;
}
// DELETE: Remove a value and maintain BST property
delete(valueToDelete) {
// Start deletion from root, update root if needed
this.root = this.deleteFromSubtree(this.root, valueToDelete);
}
deleteFromSubtree(currentNode, valueToDelete) {
// Base case: value not found in tree
const nodeNotFound = currentNode === null;
if (nodeNotFound) {
return null;
}
// Extract current value for comparison
const currentValue = currentNode.value;
// DECISION FRAMEWORK: Locate the node to delete
const searchLeft = valueToDelete < currentValue;
const searchRight = valueToDelete > currentValue;
const foundNodeToDelete = valueToDelete === currentValue;
if (searchLeft) {
// Value to delete is in left subtree
const updatedLeftSubtree = this.deleteFromSubtree(
currentNode.left,
valueToDelete
);
currentNode.left = updatedLeftSubtree;
return currentNode;
}
if (searchRight) {
// Value to delete is in right subtree
const updatedRightSubtree = this.deleteFromSubtree(
currentNode.right,
valueToDelete
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
if (foundNodeToDelete) {
// Found the node to delete - handle three cases
// DECISION FRAMEWORK: Deletion cases based on children count
const hasNoChildren =
currentNode.left === null && currentNode.right === null;
const hasOnlyRightChild =
currentNode.left === null && currentNode.right !== null;
const hasOnlyLeftChild =
currentNode.right === null && currentNode.left !== null;
const hasBothChildren =
currentNode.left !== null && currentNode.right !== null;
if (hasNoChildren) {
// Case 1: Leaf node - simply remove it
return null;
}
if (hasOnlyRightChild) {
// Case 2a: Only right child exists - replace with it
const rightChild = currentNode.right;
return rightChild;
}
if (hasOnlyLeftChild) {
// Case 2b: Only left child exists - replace with it
const leftChild = currentNode.left;
return leftChild;
}
if (hasBothChildren) {
// Case 3: Both children exist - use successor strategy
// Find the inorder successor (smallest value in right subtree)
const rightSubtree = currentNode.right;
const successorNode = this.findMinimumNode(rightSubtree);
const successorValue = successorNode.value;
// Replace current node's value with successor's value
currentNode.value = successorValue;
// Remove the successor from right subtree (it has at most one child)
const updatedRightSubtree = this.deleteFromSubtree(
rightSubtree,
successorValue
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
}
}
// Helper: Find the node with minimum value in a subtree
findMinimumNode(startNode) {
// The minimum is always the leftmost node
let currentNode = startNode;
// Keep going left until we can't go further
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
// This is the leftmost (minimum) node
return currentNode;
}
// BONUS: Inorder traversal (returns sorted array)
getSortedValues() {
const sortedArray = [];
this.collectInOrder(this.root, sortedArray);
return sortedArray;
}
collectInOrder(currentNode, resultArray) {
// Base case: null node contributes nothing
const isNullNode = currentNode === null;
if (isNullNode) {
return;
}
// Inorder traversal: Left -> Current -> Right
const leftSubtree = currentNode.left;
const currentValue = currentNode.value;
const rightSubtree = currentNode.right;
// Step 1: Process all values in left subtree (smaller values)
this.collectInOrder(leftSubtree, resultArray);
// Step 2: Process current node's value
resultArray.push(currentValue);
// Step 3: Process all values in right subtree (larger values)
this.collectInOrder(rightSubtree, resultArray);
}
}
// === EXAMPLE USAGE: Music Playlist Manager ===
function demonstrateMusicPlaylist() {
const playlist = new BinarySearchTree();
// Songs to add to our playlist
const songsToAdd = [
"Bohemian Rhapsody",
"Imagine",
"Hey Jude",
"Let It Be",
"Yesterday",
"Come Together",
];
// Add each song to the playlist
console.log("=== Adding Songs to Playlist ===");
for (const songTitle of songsToAdd) {
playlist.insert(songTitle);
console.log(`✓ Added: "${songTitle}"`);
}
// Test search functionality
console.log("\n=== Testing Song Search ===");
const songToFind = "Hey Jude";
const songExists = playlist.search(songToFind);
console.log(`Does "${songToFind}" exist? ${songExists}`); // true
const missingSong = "Stairway to Heaven";
const notInPlaylist = playlist.search(missingSong);
console.log(`Does "${missingSong}" exist? ${notInPlaylist}`); // false
// Display all songs in sorted order
console.log("\n=== All Songs (Alphabetically Sorted) ===");
const allSongsInOrder = playlist.getSortedValues();
console.log(allSongsInOrder);
// Output: ["Bohemian Rhapsody", "Come Together", "Hey Jude", "Imagine", "Let It Be", "Yesterday"]
// Remove a song from playlist
console.log("\n=== Removing a Song ===");
const songToRemove = "Hey Jude";
console.log(`Removing "${songToRemove}" from playlist...`);
playlist.delete(songToRemove);
// Show updated playlist
const updatedPlaylist = playlist.getSortedValues();
console.log("Updated playlist:", updatedPlaylist);
// Output: ["Bohemian Rhapsody", "Come Together", "Imagine", "Let It Be", "Yesterday"]
// Visualize final tree structure
console.log("\n=== Final Tree Structure ===");
console.log(`
"Imagine"
/ \\
"Come Together" "Let It Be"
/ \\
"Bohemian Rhapsody" "Yesterday"
`);
}
// Run the demonstration
demonstrateMusicPlaylist();Doubt buster
Common doubt: "When deleting a node with two children, why do we specifically choose the inorder successor (smallest in right subtree)? Why not the inorder predecessor (largest in left subtree) or any other node?"
This seems arbitrary - the algorithm appears to work with predecessor too, so why does every textbook insist on the successor? Let's explore why this choice matters.
Why this seems arbitrary
Consider deleting node 50 with two children:
50 (delete this)
/ \
30 70
/ \ / \
20 40 60 80
Options:
1. Replace with predecessor (40) - largest in left subtree
2. Replace with successor (60) - smallest in right subtree
3. Replace with... 70? 30? Why not?Both predecessor and successor seem to work - they both maintain the BST property!
The key insight: Maintaining BST property
Here's the crucial requirement: The replacement value must be:
- Greater than ALL values in the left subtree
- Less than ALL values in the right subtree
- Easy to delete from its current position
Let's check each option:
Option 1: Inorder Predecessor (40)
Before: After replacing 50 with 40:
50 40
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 - 60 80
✓ 40 > all in left subtree (20, 30)
✓ 40 < all in right subtree (60, 70, 80)
✓ Deleting 40 from left subtree is easy (it's a leaf or has one child)Option 2: Inorder Successor (60)
Before: After replacing 50 with 60:
50 60
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 - 80
✓ 60 > all in left subtree (20, 30, 40)
✓ 60 < all in right subtree (70, 80)
✓ Deleting 60 from right subtree is easy (it's a leaf or has one child)Option 3: Random node like 70
After replacing 50 with 70:
70
/ \
30 70 (duplicate?!)
/ \ / \
20 40 60 80
✗ 70 is NOT less than all in right subtree (it equals 70, greater than 60)
✗ Creates duplicate or violates BST propertyWhy specifically successor (or predecessor)?
Mathematical guarantee: The inorder successor and predecessor are the ONLY two values that satisfy all requirements:
-
Inorder Successor = smallest value greater than deleted node
- Guaranteed > all in left subtree
- Guaranteed < all in right subtree (except itself)
- Always has at most one child (no left child by definition)
-
Inorder Predecessor = largest value less than deleted node
- Guaranteed < all in right subtree
- Guaranteed > all in left subtree (except itself)
- Always has at most one child (no right child by definition)
-
Any other value = violates BST property for at least one subtree
Why successor is slightly preferred
While both work correctly, successor is often chosen for consistency:
- Standard convention: Most textbooks use successor for uniformity
- Balancing consideration: In random deletions, alternating might balance better
- Implementation simplicity: Finding minimum (leftmost) is often cleaner than finding maximum
- Historical precedent: Early BST papers used successor
The beautiful property: Why successor/predecessor have at most one child
This is the elegant part that makes deletion efficient:
Inorder Successor (smallest in right subtree):
Node
\
Right Subtree
/
Successor (no left child!)
\
Maybe right child- If successor had a left child, that child would be smaller
- But then IT would be the successor, not this node
- Contradiction! So successor can only have right child
Inorder Predecessor (largest in left subtree):
Node
/
Left Subtree
\
Predecessor (no right child!)
/
Maybe left child- If predecessor had a right child, that child would be larger
- But then IT would be the predecessor, not this node
- Contradiction! So predecessor can only have left child
This property guarantees that when we delete the successor/predecessor from its position, we only face Case 1 (leaf) or Case 2 (one child) - never the complex Case 3 again!
Concrete example: Why the algorithm is optimal
Let's trace through a deletion to see why this approach is elegant:
// Delete 50 from this tree:
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80
// \
// 65
deleteNode(root, 50):
// Found node 50 - has two children
// Find successor: go right once, then left until null
successor = findMin(70's subtree) = 60
// Replace 50's value with 60
node.value = 60
// Now delete 60 from right subtree
// 60 has one child (65), so this is Case 2 - simple!
// Final tree:
// 60
// / \
// 30 70
// / \ / \
// 20 40 65 80The algorithm elegantly reduces the complex two-children case to a simpler one-child case!
The bottom line: Using inorder successor (or predecessor) isn't arbitrary - they're the ONLY values that maintain the BST property when replacing a deleted node. The choice between them is a minor implementation detail, but the mathematical requirement for using one of them is absolute.