We've spent a lot of time on linear data structures, but in the real world, scanning through a million records one by one is a great way to make your application feel sluggish. Today, we're building a Binary Search Tree (BST). To keep this concrete, let's imagine we're building a simple Employee ID Registry. We need to store employee IDs and be able to find them almost instantly, regardless of how many people we hire.

The building block for our registry

A BST is essentially a collection of nodes. Each node needs to hold the data (the employee ID) and have pointers to two potential children: one for values smaller than itself and one for values larger. I always start by defining a lean Node class to keep the logic separate from the tree management.

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

Getting data into the tree

Now we need the actual EmployeeRegistry class. The core of a BST is the insert method. The logic is recursive: if the tree is empty, the new node becomes the root. Otherwise, we compare the new ID to the current node. Smaller goes left, larger goes right. I prefer using a helper method for the recursion so the public insert call stays clean.

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

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

  _insertNode(node, newNode) {
    if (newNode.id < node.id) {
      if (!node.left) {
        node.left = newNode;
        return;
      }
      this._insertNode(node.left, newNode);
    } else {
      if (!node.right) {
        node.right = newNode;
        return;
      }
      this._insertNode(node.right, newNode);
    }
  }
}

Wait, I forgot about duplicates

I just ran a quick test and realized I made a classic mistake. If I insert the same employee ID twice, my current logic just shoves it into the right subtree. In a registry, IDs must be unique. Having duplicate IDs in a BST doesn't break the tree, but it breaks the business logic. I need to add a guard clause to handle this.

I'll modify the _insertNode method to simply return if the IDs match. It's a small change, but it's the difference between a buggy registry and a reliable one.

_insertNode(node, newNode) {
  if (newNode.id === node.id) {
    console.log("ID already exists!");
    return; // Don't insert duplicates
  }
  
  if (newNode.id < node.id) {
    // ... rest of the logic remains the same

Finding a needle in the haystack

The whole reason we're doing this is for the search speed. Instead of checking every single ID, we can discard half the tree with every single comparison. This is where the "Binary" part of the name really pays off. If the ID we're looking for is smaller than the current node, we don't even look at the right side of the tree.

search(id) {
  if (!this.root) return false;
  return this._searchNode(this.root, id);
}

_searchNode(node, id) {
  if (!node) return false;
  if (node.id === id) return true;

  if (id < node.id) {
    return this._searchNode(node.left, id);
  } else {
    return this._searchNode(node.right, id);
  }
}

If you trace this, you'll see it's incredibly efficient. Even with a million employees, if the tree is balanced, we can find any specific ID in about 20 steps. That's the power of logarithmic time complexity.

📋 Practical Task

Implementing an In-Order Traversal for the Employee Registry

One of the most useful features of a BST is that if you traverse it "in-order" (Left, Root, Right), you get all the data back in sorted order. Currently, our EmployeeRegistry can insert and search, but it can't list all employees by their ID.

Your Task: Add a method called listAllIds() to the EmployeeRegistry class. This method should return an array containing all employee IDs sorted from smallest to largest.

• Create a helper method _inOrderTraversal(node, result = []).
• The helper should recursively visit the left child, push the current node's ID to the array, and then recursively visit the right child.
• The main listAllIds() method should call this helper starting at the root and return the final array.