How to Implement Binary Search Tree in JavaScript: Simple Guide

To implement a binary search tree in JavaScript, create a Node class with value, left, and right properties, then build a BinarySearchTree class with methods to insert and search nodes. This structure keeps smaller values on the left and larger on the right, allowing efficient data lookup.

Syntax

The binary search tree uses two main classes: Node and BinarySearchTree.

• Node holds a value and references to left and right child nodes.
• BinarySearchTree manages the root node and provides methods like insert and search.

javascript

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) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}

Example

This example shows how to create a binary search tree, insert values, and search for a value.

javascript

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) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(7);

console.log(bst.search(7));  // true
console.log(bst.search(3));  // false

Output

true
false

Common Pitfalls

Common mistakes include:

• Not handling the empty tree case when inserting the first node.
• Inserting duplicate values without a clear rule (usually duplicates go to the right or are ignored).
• Incorrectly updating current pointer causing infinite loops.
• Not returning after inserting a node, which can cause unexpected behavior.

javascript

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

  // Wrong: missing return after inserting node
  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      // Missing return here causes infinite loop
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }
}

Quick Reference

• Node: Holds value, left, and right pointers.
• Insert: Compare value, go left if smaller, right if larger, insert at null spot.
• Search: Traverse tree comparing values until found or null.
• Duplicates: Decide policy (usually insert right or ignore).

Key Takeaways

Create a Node class with value, left, and right properties to represent tree nodes.

Use a BinarySearchTree class to manage nodes with insert and search methods.

Always handle the empty tree case when inserting the first node.

Traverse left for smaller values and right for larger values during insert and search.

Avoid infinite loops by returning immediately after inserting a new node.