javascriptroom blog

Binary Search Tree in JavaScript

In the world of computer science and data handling, data structures play a crucial role. They help in organizing, storing, and retrieving data effectively. One such important data structure is the Binary Search Tree (BST). A Binary Search Tree is a sorted binary tree where each node has a value, and all the nodes in its left subtree have values less than the node's value, while all the nodes in its right subtree have values greater than the node's value. This property makes searching, insertion, and deletion operations efficient in a BST.

In this blog, we will explore the Binary Search Tree in detail, including its basic concepts, implementation in JavaScript, common operations like insertion, deletion, and searching, and best practices.

2026-07

Table of Contents#

  1. Basic Concepts of Binary Search Tree
  2. Implementation of Binary Search Tree in JavaScript
  3. Common Operations on Binary Search Tree
  4. Traversal of Binary Search Tree
  5. Best Practices
  6. Example Usage
  7. Conclusion
  8. References

Basic Concepts of Binary Search Tree#

A Binary Search Tree consists of nodes, each having a value, a left child, and a right child. The root node is the top - most node in the tree. The left and right subtrees of every node are also binary search trees.

  • Key Property: For any given node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This property enables efficient search operations as we can quickly eliminate half of the tree at each step.
  • Height: The height of a BST is the maximum number of edges from the root to a leaf node. A balanced BST has a height of O(log n), where n is the number of nodes in the tree. In a skewed BST, the height can be O(n), which makes the operations less efficient.

Implementation of Binary Search Tree in JavaScript#

We can implement a Binary Search Tree in JavaScript using an object - oriented approach. First, we need to define a TreeNode class that represents a single node in the tree, and then a BinarySearchTree class that manages the tree.

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
 
class BinarySearchTree {
    constructor() {
        this.root = null;
    }
}

Common Operations on Binary Search Tree#

Insertion#

The insertion operation in a Binary Search Tree involves finding the correct position for a new node based on the BST property. We start from the root and compare the new value with the current node's value. If the new value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. We repeat this process until we find an empty position to insert the new node.

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
 
    insert(value) {
        const newNode = new TreeNode(value);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
 
    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
}

Searching#

Searching in a Binary Search Tree is efficient due to its sorted nature. We start from the root and compare the target value with the current node's value. If they are equal, we have found the node. If the target value is less than the current node's value, we move to the left subtree; otherwise, we move to the right subtree. We repeat this process until we find the node or reach a leaf node.

class BinarySearchTree {
    // ... existing code ...
 
    search(value) {
        return this.searchNode(this.root, value);
    }
 
    searchNode(node, value) {
        if (node === null) {
            return false;
        }
        if (value === node.value) {
            return true;
        }
        if (value < node.value) {
            return this.searchNode(node.left, value);
        } else {
            return this.searchNode(node.right, value);
        }
    }
}

Deletion#

Deletion is a more complex operation in a Binary Search Tree. There are three cases to consider when deleting a node:

  1. Node is a leaf: If the node to be deleted is a leaf node (has no children), we simply remove it.
  2. Node has one child: If the node has only one child, we replace the node with its child.
  3. Node has two children: If the node has two children, we find the in - order successor (the smallest node in the right subtree) or the in - order predecessor (the largest node in the left subtree), replace the node's value with the successor's value, and then delete the successor node.
class BinarySearchTree {
    // ... existing code ...
 
    delete(value) {
        this.root = this.deleteNode(this.root, value);
    }
 
    deleteNode(node, value) {
        if (node === null) {
            return null;
        }
        if (value < node.value) {
            node.left = this.deleteNode(node.left, value);
            return node;
        } else if (value > node.value) {
            node.right = this.deleteNode(node.right, value);
            return node;
        } else {
            // Case 1: No child or one child
            if (node.left === null) {
                return node.right;
            } else if (node.right === null) {
                return node.left;
            }
            // Case 2: Two children
            const minValue = this.findMinValue(node.right);
            node.value = minValue;
            node.right = this.deleteNode(node.right, minValue);
            return node;
        }
    }
 
    findMinValue(node) {
        while (node.left !== null) {
            node = node.left;
        }
        return node.value;
    }
}

Traversal of Binary Search Tree#

Traversal is the process of visiting all the nodes in a tree. There are three common ways to traverse a Binary Search Tree:

In-order Traversal#

In - order traversal visits the nodes in ascending order of their values. It first traverses the left subtree, then the root, and finally the right subtree.

class BinarySearchTree {
    // ... existing code ...
 
    inOrderTraversal(node = this.root) {
        const result = [];
        if (node !== null) {
            result.push(...this.inOrderTraversal(node.left));
            result.push(node.value);
            result.push(...this.inOrderTraversal(node.right));
        }
        return result;
    }
}

Pre-order Traversal#

Pre - order traversal visits the root first, then the left subtree, and finally the right subtree.

class BinarySearchTree {
    // ... existing code ...
 
    preOrderTraversal(node = this.root) {
        const result = [];
        if (node !== null) {
            result.push(node.value);
            result.push(...this.preOrderTraversal(node.left));
            result.push(...this.preOrderTraversal(node.right));
        }
        return result;
    }
}

Post-order Traversal#

Post - order traversal visits the left subtree first, then the right subtree, and finally the root.

class BinarySearchTree {
    // ... existing code ...
 
    postOrderTraversal(node = this.root) {
        const result = [];
        if (node !== null) {
            result.push(...this.postOrderTraversal(node.left));
            result.push(...this.postOrderTraversal(node.right));
            result.push(node.value);
        }
        return result;
    }
}

Best Practices#

  • Balancing the Tree: As mentioned earlier, a balanced BST has a height of O(log n), which makes operations like searching, insertion, and deletion more efficient. In JavaScript, we can implement self - balancing BSTs like AVL trees or Red - Black trees to maintain balance.
  • Error Handling: When implementing operations on a BST, it is important to handle edge cases such as inserting a duplicate value, searching for a non - existent value, or deleting a non - existent node.
  • Commenting and Documentation: Since BST operations can be complex, it is a good practice to comment the code and provide proper documentation to make it more understandable for other developers.

Example Usage#

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
 
console.log(bst.search(7)); // true
console.log(bst.search(20)); // false
 
console.log(bst.inOrderTraversal()); // [3, 5, 7, 10, 15]
 
bst.delete(5);
console.log(bst.inOrderTraversal()); // [3, 7, 10, 15]

Conclusion#

Binary Search Trees are a powerful data structure in computer science. They provide an efficient way to store and retrieve sorted data. In JavaScript, we can easily implement a Binary Search Tree using object - oriented programming concepts. By understanding the basic concepts, common operations, and traversal methods, we can use BSTs effectively in various applications such as searching algorithms, sorting algorithms, and database indexing.

References#