Binary Search Trees — Search & Insert Visualized
Learn BSTs — left less, right greater, O(log n) search/insert, interactive visualizer, code breakdown, and auto-complete examples.
Introduction
Binary search trees (BST) maintain order: left < root < right at every node. Search, insert, and delete average O(log n) — degrading to O(n) if unbalanced.
Quick index
1. BST property
For every node n:
- All values in left subtree <
n.value - All values in right subtree >
n.value
In-order traversal yields sorted ascending order.
2. Interactive visualizer
Binary Search Trees
Ordered binary tree — search, insert, delete in O(log n) average when balanced.
Left subtree < root < right subtree — enables O(log n) search when balanced.
BST property
// for every node n: // all left descendants < n.value // all right descendants > n.value
In-order traversal of a BST yields sorted order.
Search avg
O(log n)
Search worst
O(n)
In-order
Sorted
3. Full implementation
class BSTNode {
constructor(value) {
this.value = value
this.left = null
this.right = null
}
}
class BST {
constructor() {
this.root = null
}
search(value) {
return this._search(this.root, value)
}
_search(node, value) {
if (!node) return false
if (value === node.value) return true
return value < node.value ? this._search(node.left, value) : this._search(node.right, value)
}
insert(value) {
this.root = this._insert(this.root, value)
}
_insert(node, value) {
if (!node) return new BSTNode(value)
if (value < node.value) node.left = this._insert(node.left, value)
else if (value > node.value) node.right = this._insert(node.right, value)
return node
}
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
}
}Function calls with output
// ── Demo calls — output shown on the right ──
const bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(10)
bst.insert(6)
bst.insert(1)
bst.search(6) // → true
bst.search(99) // → false
bst.inOrder() // → [1, 3, 6, 8, 10]4. Complexity
| Operation | Average | Worst (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
5. Real-life examples
| Scenario | BST role |
|---|---|
| Auto-complete index | Sorted word lookup and prefix search |
| Database indexes | B-tree variant for range queries |
| Ordered set (Java TreeSet) | In-memory sorted collection |
| Event timeline | Insert/search events by timestamp |
Auto-complete index
BST stores sorted strings — search prefix by traversing left/right.
Words inserted in BST order for O(log n) lookup.
Real-world implementation
class BST {
insert(word) { /* standard BST insert */ }
search(word) { /* compare and branch */ }
startsWith(prefix) { /* find node, DFS collect */ }
}Full working code for the scenario above.
Function calls with output
| // ── Function calls with output ── | |
| bst.insert("cat") | |
| bst.insert("car") | → left of cat |
| bst.insert("dog") | → right of cat |
Side output shows return value after each call — step through to trace execution.
Summary
BST = ordered binary tree — fast search when balanced. Self-balancing variants fix the O(n) worst case.
Next reads: AVL Trees · In-order Traversal
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime