How to implement a binary search tree using JavaScript

One of the most commonly used and discussed data structures in computer science is the binary search tree. This is often the first data structure introduced with a non-linear insertion algorithm. A binary search tree is similar to a doubly linked list, with each node containing some data, and two pointers to other nodes; they differ in the way these nodes relate to each other. The pointers of a binary search tree node are usually called "left" and "right" to indicate the subtree associated with the current value. A simple JavaScript implementation of this node is as follows:

var node = {
  value: 125,
  left: null,
  right: null
};

As the name suggests, a binary search tree is organized into a hierarchical tree structure. The first item becomes the root node, and each additional value is added to the tree as an ancestor of that root. However, the values ​​at the nodes of a binary search tree are unique and are ordered according to the values ​​they contain: the value in the left subtree of a node is always less than the value of the node, and the value in the right subtree is always greater than the value of the node. In this way, finding a value in a binary search tree becomes very simple. If the value you are looking for is less than the node you are processing, go left. If the value is greater, go right. There cannot be duplicates in a binary search tree because duplication would break the relationship. The following diagram represents a simple binary search tree.

The figure above represents a binary search tree whose root value is 8. When the value 3 is added, it becomes the left child of the root because 3 is less than 8. When the value 1 is added, it becomes the left child of 3 because 1 is less than 8 (so left) and then 1 is less than 3 (left again). When the value 10 is added, it becomes the right child of the root because 10 is greater than 8. This process continues with the values ​​6, 4, 7, 14, and 13. The depth of this binary search tree is 3, which means the node farthest from the root is three nodes.

Binary search trees end up in a naturally sorted order, so they can be used to find data quickly because you can immediately eliminate possibilities at each step. By limiting the number of nodes that need to be looked up, searches can be performed faster. Suppose you want to find the value 6 in the above tree. Starting at the root, determine that 6 is less than 8, so go to the left child of the root. Since 6 is greater than 3, you will go to the right node. You will find the correct value. So you only have to visit three instead of nine nodes to find the value.

To implement a binary search tree in JavaScript, the first step is to define the basic interface:

function BinarySearchTree() {
  this._root = null;
}

BinarySearchTree.prototype = {

  //restore constructor
  constructor: BinarySearchTree,

  add: function (value) {
  },

  contains: function(value){
  },

  remove: function(value){
  },

  size: function(){
  },

  toArray: function(){
  },

  toString: function(){
  }

};

Basic connections are similar to other data structures, with methods for adding and removing values. I also added some convenience methods, size(), toArray(), and toString(), which are useful for JavaScript.

To get started with using a binary search tree, a good place to start is with the contains() method. The contains() method accepts a value as an argument and returns true if the value exists in the tree, otherwise it returns false. This method follows a basic binary search algorithm to determine if the value exists:

BinarySearchTree.prototype = {

  //more code

  contains: function(value){
    var found = false,
      current = this._root

    //make sure there's a node to search
    while(!found && current){

      //if the value is less than the current node's, go left
      if (value < current.value){
        current = current.left;

      //if the value is greater than the current node's, go right
      } else if (value > current.value){
        current = current.right;

      //values ​​are equal, found it!
      } else {
        found = true;
      }
    }

    //only proceed if the node was found
    return found;
  },

  //more code

};

The search starts at the root of the tree. If no data is added, you probably don't have root, so that's got to be checked. Traversing the tree follows the simple algorithm discussed earlier: move left if the value you are looking for is less than the current node, and move right if the value is greater. The current pointer is overwritten each time until the value is found (in which case found is set to true) or there are no more nodes in that direction (in which case the value is not in the tree).

The method used in contains() can also be used to insert new values ​​into the tree. The main difference is that instead of looking up a value in a tree, you're looking for a location to put the new value:

BinarySearchTree.prototype = {

  //more code

  add: function(value){
    //create a new item object, place data in
    var node = {
        value: value,
        left: null,
        right: null
      },

      //used to traverse the structure
      current;

    //special case: no items in the tree yet
    if (this._root === null){
      this._root = node;
    } else {
      current = this._root;

      while(true){

        //if the new value is less than this node's value, go left
        if (value < current.value){

          //if there's no left, then the new node belongs there
          if (current.left === null){
            current.left = node;
            break;
          } else {
            current = current.left;
          }

        //if the new value is greater than this node's value, go right
        } else if (value > current.value){

          //if there's no right, then the new node belongs there
          if (current.right === null){
            current.right = node;
            break;
          } else {
            current = current.right;
          }   

        //if the new value is equal to the current one, just ignore
        } else {
          break;
        }
      }
    }
  },

  //more code

};

When adding values ​​to a binary search tree, a special case is when there is no root. In this case, just setting the root to the new value will easily do the job. For the other cases, the basic algorithm is exactly the same as that used in contains(): the new node goes left if it is smaller than the current value, and goes right if it is larger. The main difference is that when you can't go any further, this is where the new value goes. So if you need to move left but there is no left node, the new value will be the left node (same as the right node). Since there are no duplicates, the operation stops if a node with the same value is found.

Before moving on to the size() method, I want to discuss tree traversal in depth. To calculate the size of a binary search tree, it is necessary to visit every node in the tree. Binary search trees usually have different types of traversal methods, the most common of which is in-order traversal. Perform an in-order traversal at each node by processing the left subtree, then the node itself, then the right subtree. Since binary search trees are sorted in this way, from left to right, the result is that the nodes are processed in the correct sorted order. The order of node traversal is not actually important for the size() method, but it is important for the toArray() method. Since both methods need to perform traversal, I decided to add a traverse() method that can be used universally:

BinarySearchTree.prototype = {

  //more code

  traverse: function(process){

    //helper function
    function inOrder(node){
      if (node){

        //traverse the left subtree
        if (node.left !== null){
          inOrder(node.left);
        }      

        //call the process method on this node
        process.call(this, node);

        //traverse the right subtree
        if (node.right !== null){
          inOrder(node.right);
        }
      }
    }

    //start with the root
    inOrder(this._root);
  },

  //more code

};

This method accepts one argument, process, which is a function that should be run on each node in the tree. This method defines a helper function called inOrder() for recursively traversing the tree. Note that the recursion only moves left and right if the current node exists (to avoid processing null multiple times). The traverse() method then traverses in order starting from the root node, and the process() function processes each node. You can then use this method to implement size(), toArray(), toString():

BinarySearchTree.prototype = {

  //more code

  size: function(){
    var length = 0;

    this.traverse(function(node){
      length++;
    });

    return length;
  },

  toArray: function(){
    var result = [];

    this.traverse(function(node){
      result.push(node.value);
    });

    return result;
  },

  toString: function(){
    return this.toArray().toString();
  },

  //more code

};

Both size() and toArray() call the traverse() method and pass in a function to run on each node. In the case of size(), the function simply increments the size variable, whereas toArray() uses a function to add the value of the node to the array. The toString() method converts the returned array to a string before calling toArray() and returns it.

When deleting a node, you need to determine if it is a root node. The root node is treated similarly to other nodes, with the notable exception that the root node needs to be set to a different value at the end. For simplicity, this will be treated as a special case in JavaScript code.

The first step to deleting a node is to determine if the node exists:

BinarySearchTree.prototype = {

  //more code here

  remove: function(value){

    var found = false,
      parent = null,
      current = this._root,
      childCount,
      replacement,
      replacementParent;

    //make sure there's a node to search
    while(!found && current){

      //if the value is less than the current node's, go left
      if (value < current.value){
        parent = current;
        current = current.left;

      //if the value is greater than the current node's, go right
      } else if (value > current.value){
        parent = current;
        current = current.right;

      //values ​​are equal, found it!
      } else {
        found = true;
      }
    }

    //only proceed if the node was found
    if (found){
      //continue
    }

  },
  //more code here

};

The first part of the remove() method is to locate the node to be removed using a binary search, moving it to the left if the value is less than the current node, or to the right if the value is greater than the current node. You also keep track of the parent node when traversing, because you will eventually need to remove the node from its parent. When found is equal to true, the value of current is the node to be deleted.

There are three conditions to note when deleting a node:

1. Leaf Node
2. A node with only one child
3. A node with two children
   

Deleting anything other than a leaf node from a binary search tree means that values ​​must be moved around to keep the tree properly sorted. The first two are relatively simple to implement and just remove a leaf node and remove a node with one child and replace it with its child. The last case is a bit more complicated to access later.

Before understanding how to delete a node, you need to know how many child nodes exist on the node. Once that's known, you have to determine if the node is a root node, leaving you with a fairly simple decision tree:

BinarySearchTree.prototype = {

  //more code here

  remove: function(value){

    var found = false,
      parent = null,
      current = this._root,
      childCount,
      replacement,
      replacementParent;

    //find the node (removed for space)

    //only proceed if the node was found
    if (found){

      //figure out how many children
      childCount = (current.left !== null ? 1 : 0) + 
             (current.right !== null ? 1 : 0);

      //special case: the value is at the root
      if (current === this._root){
        switch(childCount){

          //no children, just erase the root
          case 0:
            this._root = null;
            break;

          //one child, use one as the root
          case 1:
            this._root = (current.right === null ? 
                   current.left : current.right);
            break;

          //two children, little work to do
          case 2:

            //TODO

          //no default

        }    

      //non-root values
      } else {

        switch (childCount) {

          //no children, just remove it from the parent
          case 0:
            //if the current value is less than its 
            //parent's, null out the left pointer
            if (current.value < parent.value){
              parent.left = null;

            //if the current value is greater than its
            //parent's, null out the right pointer
            } else {
              parent.right = null;
            }
            break;

          //one child, just reassign to parent
          case 1:
            //if the current value is less than its 
            //parent's, reset the left pointer
            if (current.value < parent.value){
              parent.left = (current.left === null ? 
                      current.right : current.left);

            //if the current value is greater than its 
            //parent's, reset the right pointer
            } else {
              parent.right = (current.left === null ? 
                      current.right : current.left);
            }
            break;  

          //two children, a bit more complicated
          case 2:

            //TODO     

          //no default

        }

      }

    }

  },

  //more code here

};

When dealing with the root node, it's a simple process of overwriting it. For non-root nodes, the corresponding pointers on parent must be set according to the value of the node to be deleted: if the value deleted is less than the parent, the left pointer must be reset to null (for a node with no children) or the left pointer of the deleted node; if the value deleted is greater than the parent, the right pointer must be reset to null or the right pointer of the deleted node.

As mentioned before, deleting a node with two children is the most complex operation. The following figure is a representation of the catechu search tree.

The root is 8 and the left child is 3. What will happen if 3 is deleted? There are two possibilities: 1 (the left child of 3, called the in-order predecessor) or 4 (the leftmost child of the right subtree, called the in-order successor) can both replace 3.

Either of these two options is appropriate. To find the in-order predecessor, that is, the value before the value you delete, check the left subtree of the node you want to delete and choose the rightmost child; to find the in-order successor, the value that comes immediately after the value you delete, reverse the process and check the leftmost right subtree. Each of these requires another pass through the tree to complete the operation:

BinarySearchTree.prototype = {

  //more code here

  remove: function(value){

    var found = false,
      parent = null,
      current = this._root,
      childCount,
      replacement,
      replacementParent;

    //find the node (removed for space)

    //only proceed if the node was found
    if (found){

      //figure out how many children
      childCount = (current.left !== null ? 1 : 0) + 
             (current.right !== null ? 1 : 0);

      //special case: the value is at the root
      if (current === this._root){
        switch(childCount){

          //other cases removed to save space

          //two children, little work to do
          case 2:

            //new root will be the old root's left child
            //... maybe
            replacement = this._root.left;

            //find the right-most leaf node to be 
            //the real new root
            while (replacement.right !== null){
              replacementParent = replacement;
              replacement = replacement.right;
            }

            //it's not the first node on the left
            if (replacementParent !== null){

              //remove the new root from it's 
              //previous position
              replacementParent.right = replacement.left;

              //give the new root all of the old 
              //root's children
              replacement.right = this._root.right;
              replacement.left = this._root.left;
            } else {

              //just assign the children
              replacement.right = this._root.right;
            }

            //officially assign new root
            this._root = replacement;

          //no default

        }    

      //non-root values
      } else {

        switch (childCount) {

          //other cases removed to save space

          //two children, a bit more complicated
          case 2:

            //reset pointers for new traversal
            replacement = current.left;
            replacementParent = current;

            //find the right-most node
            while(replacement.right !== null){
              replacementParent = replacement;
              replacement = replacement.right;
            }

            replacementParent.right = replacement.left;

            //assign children to the replacement
            replacement.right = current.right;
            replacement.left = current.left;

            //place the replacement in the right spot
            if (current.value < parent.value){
              parent.left = replacement;
            } else {
              parent.right = replacement;
            }     

          //no default

        }

      }

    }

  },

  //more code here

};

The code for a root node and a non-root node with two children is almost identical. This implementation always finds the in-order predecessor by looking in the left subtree and finding the rightmost child. The traversal is done using the replacement and replacementParent variables in a while loop. The node in replacement ends up being the node that replaces current, so it is removed from its current position by setting its parent's right pointer to the replacement's left pointer. For the root node, when replacement is a direct child of the root node, replacementParent will be null, so replacement's right pointer is simply set to root's right pointer. The final step is to assign the replacement nodes to the correct locations. For root nodes, the replacement is set to the new root; for non-root nodes, the replacement is assigned to the appropriate position on the original parent.

Note: Always replacing nodes with their in-order predecessors can lead to an unbalanced tree where most values ​​are on one side of the tree. An unbalanced tree means a less efficient search, so it should be a concern in real scenarios. In a binary search tree implementation, it is necessary to decide whether to use in-order predecessors or in-order successors so that the tree remains properly balanced (often called a self-balancing binary search tree).

Summarize

This is the end of this article on how to use JavaScript to implement a binary search tree. For more relevant JavaScript binary search tree content, please search 123WORDPRESS.COM’s previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!