Implementing Binary Search Trees with NodeJS and Javascript

Keep data sorted while inserting and searching without resorting the whole array? A BST gives O(log n) on average — unless it unbalances.

What you'll learn:

• left < node < right
• insert, search, traversals
• degenerate BST on sorted input
• connection to database indexes

Prerequisites: trees (ep. 6).

BST: binary search in a tree

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.

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.

Hands-on

First The Theory

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):

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.

Now The Practice

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.js

Expected 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 found

AWESOME!

Look 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:

1. Leaf node (no children) — just remove it.
2. One child — replace the node with its child.
3. Two children — replace the node's value with its in-order successor (the smallest value in its right subtree), then delete that successor.

Give it a shot as a challenge—if you get stuck, drop a comment and we'll work through it together.

Edge cases: skewed BST and deletion

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.

TL;DR — BST

Next steps

• Tries (ep. 13)
• Binary search on arrays (ep. 16)

Before you go

Do you debug BSTs with in-order walks? Comment if removal tripped you up.