Implementing a BST in JavaScript

A Binary Search Tree (BST) is one of the most fundamental data structures in computer science, and implementing one from scratch in JavaScript is an excellent way to solidify both your understanding of the structure and your ability to reason about recursive algorithms. A BST organizes values so that, at every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property makes searching, inserting, and deleting values dramatically more efficient than scanning a flat list — provided the tree stays reasonably balanced. In this topic we will build a complete, working BST in JavaScript step by step, covering every operation with full code, detailed explanation, and illustrative examples.

Defining the Node Class

Every element stored in a BST lives inside a node. A node is a small container that holds three things: the data value itself, a pointer to its left child, and a pointer to its right child. When a node is first created it has no children, so both pointers start as null. That null state is exactly what distinguishes a leaf node (a node with no children) from an internal node.

Using a JavaScript class gives us a clean, repeatable way to stamp out new nodes throughout the life of the tree. Every call to new Node(value) produces an object with identical structure, which means insertion and other operations can always rely on the same property names without any defensive checks.

class Node {
  constructor(value) {
    this.value = value;   // the data stored in this node
    this.left  = null;    // pointer to the left child (smaller values)
    this.right = null;    // pointer to the right child (larger values)
  }
}

For example, new Node(42) creates an object { value: 42, left: null, right: null }. Because both child pointers are null, the node is technically a complete, valid BST all by itself — a tree of size one.

Setting Up the BinarySearchTree Class

The tree itself is managed by a separate class whose job is to track the root — the topmost node from which every other node is reachable. When the tree is first created, no nodes exist, so the root is null. Every operation (insert, search, delete, traversal) is added as a method on this class, which keeps all the logic in one place and prevents outside code from directly overwriting the root and corrupting the structure.

class BinarySearchTree {
  constructor() {
    this.root = null;   // empty tree: no root yet
  }
}

Encapsulation matters here. If root were a bare global variable, any part of your program could accidentally set it to undefined or point it at the wrong node. Tucking it inside the class means the only way to interact with the tree is through the methods you deliberately design — a much safer contract.

Implementing the Insert Method

Insertion is the operation that builds the tree. The BST property dictates exactly where every new value must go: travel left when the new value is smaller than the current node, travel right when it is larger, and keep going until you reach a null slot. That slot is exactly where the new node belongs.

Two special situations need handling. First, if the tree is completely empty (this.root === null), the new node simply becomes the root. Second, duplicate values need a defined policy. The most common convention is to ignore duplicates entirely (treating the BST as a set), though you could instead place duplicates consistently to the right.

Recursion is the natural fit here because the problem at each node is identical to the overall problem: "Where in this subtree does the new value belong?" A helper method accepts both the current node and the value to insert, and returns the (possibly updated) subtree root so that parent pointers update automatically without extra bookkeeping.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;   // first insertion: new node becomes root
      return this;
    }
    this._insertNode(this.root, newNode);
    return this;
  }

  _insertNode(current, newNode) {
    if (newNode.value === current.value) {
      return;   // duplicate: ignore
    }
    if (newNode.value < current.value) {
      // go left
      if (current.left === null) {
        current.left = newNode;       // found the empty slot
      } else {
        this._insertNode(current.left, newNode);   // keep descending
      }
    } else {
      // go right
      if (current.right === null) {
        current.right = newNode;
      } else {
        this._insertNode(current.right, newNode);
      }
    }
  }
}

Consider inserting the sequence 10, 5, 15, 3, 7:

• 10 — tree is empty, becomes root.
• 5 — 5 < 10, go left; left is null → insert here. Root's left child is now 5.
• 15 — 15 > 10, go right; right is null → insert here. Root's right child is now 15.
• 3 — 3 < 10, go left to 5; 3 < 5, go left; null → insert. Node 5's left child is 3.
• 7 — 7 < 10, go left to 5; 7 > 5, go right; null → insert. Node 5's right child is 7.

The result is a balanced-looking tree. In-order traversal (explained below) would yield 3, 5, 7, 10, 15 — perfectly sorted.

Implementing Search / Lookup

Searching exploits the BST property to eliminate half the remaining tree at each step. Start at the root. If the target matches the current node's value, you found it. If the target is smaller, move left; if larger, move right. If you ever reach null, the value is not in the tree.

// Add this method to BinarySearchTree
find(value) {
  return this._findNode(this.root, value);
}

_findNode(current, value) {
  if (current === null) {
    return false;           // fell off the tree: value not found
  }
  if (value === current.value) {
    return true;            // exact match
  }
  if (value < current.value) {
    return this._findNode(current.left, value);
  } else {
    return this._findNode(current.right, value);
  }
}

Using the tree built above (10, 5, 15, 3, 7):

• find(7) → compare 7 with 10 (go left), compare 7 with 5 (go right), compare 7 with 7 → true.
• find(9) → compare 9 with 10 (go left), compare 9 with 5 (go right), compare 9 with 7 (go right), null → false.

The time complexity of search is O(log n) for a balanced BST because each comparison halves the search space. In the worst case — a tree that has degenerated into a linked list because values were inserted in sorted order — every node must be visited, giving O(n). This is why self-balancing trees (AVL, Red-Black) exist, though they are beyond the scope of this implementation.

Implementing BST Traversal Methods

Traversal means visiting every node in the tree in a specific order. There are three classic depth-first traversal orders, each with a different visit sequence relative to a node's subtrees. A fourth strategy, breadth-first (level-order) traversal, uses a queue rather than recursion, but the three recursive patterns are the most commonly tested.

All three can be implemented by pushing visited values into an array that is returned at the end, or by calling a user-supplied callback for each node. The array approach is often easier to test because you can compare the output directly.

// Add these methods to BinarySearchTree

// In-order: Left → Node → Right  (sorted ascending)
inOrder(node = this.root, result = []) {
  if (node !== null) {
    this.inOrder(node.left, result);
    result.push(node.value);
    this.inOrder(node.right, result);
  }
  return result;
}

// Pre-order: Node → Left → Right  (root first)
preOrder(node = this.root, result = []) {
  if (node !== null) {
    result.push(node.value);
    this.preOrder(node.left, result);
    this.preOrder(node.right, result);
  }
  return result;
}

// Post-order: Left → Right → Node  (root last)
postOrder(node = this.root, result = []) {
  if (node !== null) {
    this.postOrder(node.left, result);
    this.postOrder(node.right, result);
    result.push(node.value);
  }
  return result;
}

For the tree containing 10, 5, 15, 3, 7:

• In-order: [3, 5, 7, 10, 15] — always sorted ascending, a quick sanity check that the BST property holds.
• Pre-order: [10, 5, 3, 7, 15] — the root appears first; feeding these values into a fresh BST's insert method would rebuild an identical tree.
• Post-order: [3, 7, 5, 15, 10] — the root appears last; every node is processed only after both its subtrees are done, ideal for cleanup operations.

Implementing the Delete Method

Deletion is the most complex BST operation because removing a node must preserve the BST property for the entire remaining tree. There are exactly three cases based on how many children the target node has.

Case 1 — Leaf node (no children): Simply set the parent's pointer that pointed to this node to null. The node is disconnected and will be garbage collected.

Case 2 — One child: Bypass the deleted node by pointing the parent directly at the node's only child. The subtree rooted at that child is still valid because it always satisfied the BST property relative to the deleted node, and therefore also relative to the deleted node's parent.

Case 3 — Two children: This case cannot be solved by simple pointer manipulation. Instead, we find the in-order successor — the smallest value in the right subtree, i.e., the leftmost node of the right child. This value is guaranteed to be larger than everything in the left subtree (because it came from the right) and smaller than everything else in the right subtree (because it is the minimum there). We copy its value into the node being "deleted," then delete the in-order successor from the right subtree — which is now guaranteed to be either a leaf or a node with only a right child (it had no left child by definition, since it was the leftmost).

The recursive approach handles parent-pointer updates automatically: each call returns the updated subtree root, and the caller assigns that return value to its own left or right pointer.

// Add these methods to BinarySearchTree

delete(value) {
  this.root = this._deleteNode(this.root, value);
  return this;
}

_deleteNode(current, value) {
  if (current === null) {
    return null;   // value not found; nothing to delete
  }

  if (value < current.value) {
    // target is in the left subtree
    current.left = this._deleteNode(current.left, value);

  } else if (value > current.value) {
    // target is in the right subtree
    current.right = this._deleteNode(current.right, value);

  } else {
    // ---- found the node to delete ----

    // Case 1: leaf node
    if (current.left === null && current.right === null) {
      return null;
    }

    // Case 2a: only right child
    if (current.left === null) {
      return current.right;
    }

    // Case 2b: only left child
    if (current.right === null) {
      return current.left;
    }

    // Case 3: two children — find in-order successor (min of right subtree)
    const successor = this._findMin(current.right);
    current.value = successor.value;          // overwrite with successor value
    current.right = this._deleteNode(current.right, successor.value); // remove successor
  }

  return current;   // return updated subtree root so parent can relink
}

_findMin(node) {
  while (node.left !== null) {
    node = node.left;
  }
  return node;
}

Walking through an example with the tree 10, 5, 15, 3, 7, 12, 20:

• Delete 3 (leaf): Node 5's left pointer becomes null. Tree: 10, 5, 15, 7, 12, 20.
• Delete 5 (one child — only right child 7): Node 10's left pointer skips over 5 and points directly to 7. Tree: 10, 7, 15, 12, 20.
• Delete 10 (root with two children): In-order successor of 10 is 12 (leftmost of right subtree rooted at 15). Copy 12 into root, then delete 12 from the right subtree (12 is a leaf there). Tree: 12, 7, 15, 20. In-order: [7, 12, 15, 20] ✓.

Putting It All Together: Testing the BST

The best way to validate your implementation is to run it against a set of known inputs and verify the outputs match expectations. In-order traversal is your primary debugging tool: the output must always be a sorted array if the BST property holds.

const bst = new BinarySearchTree();

// Insert values
[10, 5, 15, 3, 7, 12, 20].forEach(v => bst.insert(v));

// Traversal checks
console.log(bst.inOrder());    // [3, 5, 7, 10, 12, 15, 20]  ← sorted ✓
console.log(bst.preOrder());   // [10, 5, 3, 7, 15, 12, 20]
console.log(bst.postOrder());  // [3, 7, 5, 12, 20, 15, 10]

// Search checks
console.log(bst.find(7));    // true
console.log(bst.find(99));   // false

// Delete leaf
bst.delete(3);
console.log(bst.inOrder());  // [5, 7, 10, 12, 15, 20] ✓

// Delete node with one child (5 now has only right child 7)
bst.delete(5);
console.log(bst.inOrder());  // [7, 10, 12, 15, 20] ✓

// Delete node with two children (root 10)
bst.delete(10);
console.log(bst.inOrder());  // [7, 12, 15, 20] ✓

// Edge cases
const emptyBST = new BinarySearchTree();
console.log(emptyBST.find(5));     // false — searching empty tree
console.log(emptyBST.inOrder());   // [] — traversing empty tree

// Duplicate insertion
const dupBST = new BinarySearchTree();
dupBST.insert(10).insert(10).insert(10);
console.log(dupBST.inOrder());     // [10] — duplicates ignored

Testing all three deletion cases explicitly is critical. A subtle bug in the two-child case — for instance, forgetting to recursively delete the in-order successor after copying its value — will leave a duplicate in the tree that in-order traversal will expose immediately. Similarly, always test deleting the root node, because that is the one node whose parent is not another node but rather this.root, and the recursive return-value pattern handles it correctly only if this.root is assigned the result of the initial recursive call.

A complete picture of the classes together, for reference:

class Node {
  constructor(value) {
    this.value = value;
    this.left  = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) { this.root = newNode; return this; }
    this._insertNode(this.root, newNode);
    return this;
  }

  _insertNode(current, newNode) {
    if (newNode.value === current.value) return;
    if (newNode.value < current.value) {
      if (current.left === null) current.left = newNode;
      else this._insertNode(current.left, newNode);
    } else {
      if (current.right === null) current.right = newNode;
      else this._insertNode(current.right, newNode);
    }
  }

  find(value) { return this._findNode(this.root, value); }
  _findNode(current, value) {
    if (current === null) return false;
    if (value === current.value) return true;
    return value < current.value
      ? this._findNode(current.left,  value)
      : this._findNode(current.right, value);
  }

  inOrder(node = this.root, result = []) {
    if (node !== null) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }

  preOrder(node = this.root, result = []) {
    if (node !== null) {
      result.push(node.value);
      this.preOrder(node.left,  result);
      this.preOrder(node.right, result);
    }
    return result;
  }

  postOrder(node = this.root, result = []) {
    if (node !== null) {
      this.postOrder(node.left,  result);
      this.postOrder(node.right, result);
      result.push(node.value);
    }
    return result;
  }

  delete(value) { this.root = this._deleteNode(this.root, value); return this; }
  _deleteNode(current, value) {
    if (current === null) return null;
    if (value < current.value) {
      current.left  = this._deleteNode(current.left,  value);
    } else if (value > current.value) {
      current.right = this._deleteNode(current.right, value);
    } else {
      if (!current.left && !current.right) return null;
      if (!current.left)  return current.right;
      if (!current.right) return current.left;
      const successor  = this._findMin(current.right);
      current.value    = successor.value;
      current.right    = this._deleteNode(current.right, successor.value);
    }
    return current;
  }

  _findMin(node) {
    while (node.left !== null) node = node.left;
    return node;
  }
}

With this implementation in hand you have a fully functional BST that supports insertion, lookup, all three depth-first traversals, and deletion across all three node configurations. The consistent use of recursion, the encapsulation of state inside the class, and the return-value pattern for pointer updates form patterns you will encounter repeatedly in more advanced tree algorithms and data structure work.