Binary Search Trees — Insert, Search & Delete Guide
In this tutorial, you'll learn about Binary Search Trees. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A Binary Search Tree (BST) is a Binary Tree where for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property enables O(log n) average search, insert, and delete operations.
What You'll Learn
You will learn BST properties, implement insert, search, and delete operations, handle edge cases like duplicate values and skewed trees, and validate BST correctness.
Why It Matters
BSTs provide an efficient way to maintain sorted data with dynamic insertions and deletions. They are the foundation for balanced trees (AVL, Red-Black) used in databases, file systems, and associative containers.
Real-World Use
Doda Browser's bookmark manager uses a BST to store bookmarks sorted by URL. When you add a new bookmark, it's inserted while maintaining sort order. Searching by URL happens in O(log n) instead of scanning all bookmarks.
BST Property
graph TD
R[8] --> L[3]
R --> RI[10]
L --> LL[1]
L --> LR[6]
LR --> LRL[4]
LR --> LRR[7]
RI --> RIR[14]
RI --> RIL[13]
style R fill:#4a90d9,stroke:#333,color:#fff
For each node: left subtree values < node value < right subtree values. This invariant must hold for every node, not just the root.
BST Implementation
class BSTNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = BSTNode(value)
return
self._insert(self.root, value)
def _insert(self, node, value):
if value < node.value:
if node.left:
self._insert(node.left, value)
else:
node.left = BSTNode(value)
elif value > node.value:
if node.right:
self._insert(node.right, value)
else:
node.right = BSTNode(value)
def search(self, value):
return self._search(self.root, value)
def _search(self, node, value):
if not node:
return False
if node.value == value:
return True
elif value < node.value:
return self._search(node.left, value)
else:
return self._search(node.right, value)
def delete(self, value):
self.root = self._delete(self.root, value)
def _delete(self, node, value):
if not node:
return None
if value < node.value:
node.left = self._delete(node.left, value)
elif value > node.value:
node.right = self._delete(node.right, value)
else:
if not node.left:
return node.right
if not node.right:
return node.left
successor = self._min_value_node(node.right)
node.value = successor.value
node.right = self._delete(node.right, successor.value)
return node
def _min_value_node(self, node):
while node.left:
node = node.left
return node
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.value)
self._inorder(node.right, result)
bst = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst.insert(v)
print("Inorder:", bst.inorder())
print("Search 6:", bst.search(6))
print("Search 15:", bst.search(15))
bst.delete(3)
print("After delete 3:", bst.inorder())
Expected output:
Inorder: [1, 3, 4, 6, 7, 8, 10, 13, 14]
Search 6: True
Search 15: False
After delete 3: [1, 4, 6, 7, 8, 10, 13, 14]
class BSTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() { this.root = null; }
insert(value) {
if (!this.root) { this.root = new BSTNode(value); return; }
this._insert(this.root, value);
}
_insert(node, value) {
if (value < node.value) {
if (node.left) this._insert(node.left, value);
else node.left = new BSTNode(value);
} else if (value > node.value) {
if (node.right) this._insert(node.right, value);
else node.right = new BSTNode(value);
}
}
search(value) { return this._search(this.root, value); }
_search(node, value) {
if (!node) return false;
if (node.value === value) return true;
return value < node.value
? this._search(node.left, value)
: this._search(node.right, value);
}
delete(value) { this.root = this._delete(this.root, value); }
_delete(node, value) {
if (!node) return null;
if (value < node.value) { node.left = this._delete(node.left, value); }
else if (value > node.value) { node.right = this._delete(node.right, value); }
else {
if (!node.left) return node.right;
if (!node.right) return node.left;
let successor = this._minValueNode(node.right);
node.value = successor.value;
node.right = this._delete(node.right, successor.value);
}
return node;
}
_minValueNode(node) { while (node.left) node = node.left; return node; }
inorder() {
let result = [];
this._inorder(this.root, result);
return result;
}
_inorder(node, result) {
if (node) {
this._inorder(node.left, result);
result.push(node.value);
this._inorder(node.right, result);
}
}
}
let bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(v => bst.insert(v));
console.log("Inorder:", bst.inorder());
console.log("Search 6:", bst.search(6));
bst.delete(3);
console.log("After delete 3:", bst.inorder());
Expected output:
Inorder: [ 1, 3, 4, 6, 7, 8, 10, 13, 14 ]
Search 6: true
After delete 3: [ 1, 4, 6, 7, 8, 10, 13, 14 ]
Delete Operation Cases
Deleting a node in a BST has three cases:
| Case | Description | Solution |
|---|---|---|
| Leaf | Node has no children | Remove directly |
| One child | Node has one child | Replace with its child |
| Two children | Node has both children | Find inorder successor (smallest in right subtree), copy its value, delete successor |
Validating a BST
Not every Binary Tree is a BST. The naive check (comparing only left and right children) is wrong — you must ensure the entire subtree respects the bounds.
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if not root:
return True
if root.value <= min_val or root.value >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.value) and
is_valid_bst(root.right, root.value, max_val))
Complexity Analysis
| Operation | Average | Worst (Skewed) |
|---|---|---|
| Insert | O(log n) | O(n) |
| Search | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Traversal | O(n) | O(n) |
The worst case occurs when the BST becomes a Linked List (inserting sorted values). Balanced trees like AVL and Red-Black prevent this.
Common Pitfalls
1. Not Handling Duplicates
BST behavior with duplicates varies — some insert to the left, some to the right, and some reject them. Be consistent and document your choice.
2. Incorrect Delete of Node with Two Children
Finding the inorder successor is essential. A common mistake is using the left subtree's maximum (inorder predecessor) inconsistently.
3. Forgetting to Update Parent's Pointer
When deleting a root node, the new root must be returned and assigned. Recursive implementations handle this naturally.
4. Stack Overflow from Recursion
Deep BSTs (or skewed ones) can overflow the call stack. Use iterative implementations for production code.
5. Only Checking Immediate Children for Validation
A node's left child might be smaller, but the left child's right child could violate the global BST property. Always pass min/max bounds.
Practice Questions
1. Find the kth smallest element in a BST.
2. Find the lowest common ancestor (LCA) of two nodes in a BST.
def lca(root, p, q):
while root:
if p < root.value and q < root.value:
root = root.left
elif p > root.value and q > root.value:
root = root.right
else:
return root.value
return None
3. Convert a sorted array to a balanced BST.
4. Challenge: Implement an AVL tree with automatic rebalancing after each insert and delete.
5. Real-world task: DodaZIP uses a BST to maintain sorted file entries during archive creation. Write a function that takes an unsorted list of filenames, inserts them into a BST, and returns the sorted list via inorder traversal.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro