Binary search trees in JavaScript: insert, search, traversals, and real-world limits. Full Node.js walkthrough with code.
Jonathan Juliani
Sr Software Engineer - Full Stack · WithClutch Inc. | Juliani Tecnologia
Keep data sorted while inserting and searching without resorting the whole array? A BST gives O(log n) on average — unless it unbalances.
Prerequisites: trees (ep. 6).
You've already seen binary trees in this series. A Binary Search Tree (BST) is a binary tree with an extra rule baked in: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. That single constraint is what makes searching so efficient.
scene: en/data-structures-in-a-nutshell/bst-example
Interactive Excalidraw view is not available in this build.
graph TD N8["8"] N3["3"] N10["10"] N1["1"] N6["6"] N14["14"] N4["4"] N7["7"] N13["13"] N8 --> N3 N8 --> N10 N3 --> N1 N3 --> N6 N6 --> N4 N6 --> N7 N10 --> N14 N14 --> N13
Look at the tree above. Starting from root 8: everything on the left (3, 1, 6, 4, 7) is smaller than 8, and everything on the right (10, 14, 13) is larger. That pattern repeats at every node. If I'm searching for 6, I start at 8 → go left → reach 3 → go right → reach 6. Done—three comparisons instead of scanning the whole list.
The BST ordering rule gives us a key property: an in-order traversal (left → node → right) always returns values in sorted order. So a BST is basically a sorted structure that keeps itself ordered automatically as you insert and remove values.
Operations in an ideal BST (balanced):
| Operation | Time |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
What's the catch?
The catch is balance. If you insert values in already-sorted order—say 1, 2, 3, 4, 5—every new node just goes to the right of the previous one. The tree degrades into a linked list and all operations drop to O(n). Self-balancing trees (AVL, Red-Black) fix this automatically, but we'll keep things simple here.
Open your favourite IDE, create a file called bst.js, and paste the following:
class Node {
constructor(value) {
this.value = value
this.left = null
this.right = null
}
}
class BST {
constructor() {
this.root = null
}
insert(value) {
const newNode = new Node(value)
if (!this.root) {
this.root = newNode
return this
}
let current = this.root
while (true) {
if (value === current.value) return this // ignore duplicates
if (value < current.value) {
if (!current.left) { current.left = newNode; return this }
current = current.left
} else {
if (!current.right) { current.right = newNode; return this }
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
}
}Breaking it down:
Node is just a container—a value, a left child, and a right child.BST holds the root and the methods.insert walks the tree comparing values: smaller goes left, larger goes right. When it finds an empty spot, it places the new node there.search follows the same path—left if smaller, right if larger—until it finds the value or falls off the end of the tree.Now let's add in-order traversal. This is the operation that reads the tree back in sorted order. Add this method inside the BST class:
inOrder(node = this.root, result = []) {
if (node) {
this.inOrder(node.left, result)
result.push(node.value)
this.inOrder(node.right, result)
}
return result
}The pattern is: visit left subtree first, then push the current node, then visit right subtree. Because of the BST ordering rule, this always yields a sorted array.
Let's test everything. After the BST class, add:
const tree = new BST()
tree.insert(8)
tree.insert(3)
tree.insert(10)
tree.insert(1)
tree.insert(6)
tree.insert(14)
tree.insert(4)
tree.insert(7)
tree.insert(13)
console.log('In-order traversal (should be sorted):')
console.log(tree.inOrder())
console.log('\nSearch for 6:')
const found = tree.search(6)
console.log(found ? `Found: ${found.value}` : 'Not found')
console.log('\nSearch for 99:')
const notFound = tree.search(99)
console.log(notFound ? `Found: ${notFound.value}` : 'Not found')Run it:
node bst.jsExpected output:
In-order traversal (should be sorted):
[
1, 3, 4, 6,
7, 8, 10, 13,
14
]
Search for 6:
Found: 6
Search for 99:
Not foundLook at that in-order result—[1, 3, 4, 6, 7, 8, 10, 13, 14], perfectly sorted, even though we inserted values in a random order. That's the BST rule doing its job silently on every insert.
What about deleting a node?
Deletion is the trickiest BST operation because there are three cases to handle:
Give it a shot as a challenge—if you get stuck, drop a comment and we'll work through it together.
Sorted inserts 1..n become a linked list — O(n). Production uses balanced trees or ordered Map implementations.
Deleting a node with two children needs the in-order successor — the usual manual bug.
| op | average | worst skewed |
|---|---|---|
| search | O(log n) | O(n) |
Do you debug BSTs with in-order walks? Comment if removal tripped you up.
Get architecture and performance notes in your inbox. Same list as the timed prompt—subscribe here anytime.
