Binary Search Trees (BSTs) Algorithm
A sorted array gives you fast search but slow inserts. A linked list gives you fast inserts but slow search. A Binary Search Tree tries to give you both.
20 Mar 2024
A sorted array gives you fast search but slow inserts. A linked list gives you fast inserts but slow search. A Binary Search Tree tries to give you both.
What It Does
A BST is a tree where every node follows one rule: left children are smaller, right children are larger. This structure lets you search, insert, and delete in O(log n) time — on average.
The Implementation
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
insert(value) {
const node = new TreeNode(value);
if (!this.root) { this.root = node; return; }
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) { current.left = node; return; }
current = current.left;
} else {
if (!current.right) { current.right = node; return; }
current = current.right;
}
}
}
search(value) {
let current = this.root;
while (current) {
if (value === current.value) return current;
current = value < current.value ? current.left : current.right;
}
return null;
}
inorder(node = this.root, result = []) {
if (!node) return result;
this.inorder(node.left, result);
result.push(node.value);
this.inorder(node.right, result);
return result;
}
}
const tree = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(v => tree.insert(v));
console.log(tree.search(6)); // TreeNode { value: 6, ... }
console.log(tree.inorder()); // [1, 3, 4, 6, 7, 8, 10, 13, 14]Traversals
- Inorder (left → node → right): gives sorted output.
- Preorder (node → left → right): useful for copying the tree.
- Postorder (left → right → node): useful for deleting the tree.
Complexity
| Operation | Average | Worst |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
The Trap
That O(n) worst case is real. Insert sorted data into a BST — 1, 2, 3, 4, 5 — and you get a linked list. Every operation becomes linear.
Self-balancing trees (AVL, Red-Black) fix this by rebalancing after insertions and deletions. They guarantee O(log n) worst case, at the cost of more complex insert/delete logic.
The Trade-off
BSTs give you sorted order + fast operations. But if you only need fast lookup by key, a hash map is O(1) average. If you need sorted data but don't need frequent inserts, a sorted array with binary search is simpler. BSTs shine when you need both dynamic inserts and sorted traversal.