Binary Search Tree

tejender7
Oct 29, 2022
3 min read

Updated: Feb 2, 2023

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.

Binary search trees allow binary search for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.

Operations of a Binary Search Tree

Insertion

Insertion causes BST representation to change dynamically. The data structure must be modified in such a way that the properties of BST continue to hold. New nodes are inserted as leaf nodes in the BST.

Here we insert 13 in the above BST.

Code to insert a new value

insert(item, node) {
  if(node === undefined) {
    node = this.root;
    if(this.root.item === undefined){
      this.root.item = item;
      return;
    }
  }

  if(item > node.item){
    if(!node.right){
      node.setRight(new BinaryTreeNode(item));
    } else {
      this.insert(item, node.right);
    }
  } else {
    if(!node.left){
      node.setLeft(new BinaryTreeNode(item));
    } else {
      this.insert(item, node.left);
    }
  }
}

Search

Searching begins by examining the root node. If the tree is undefined, the key being searched for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful, and true is returned. If the key is less than that of the root, the search proceeds by examining the left subtree. Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree. This process is repeated until the key is found or the remaining subtree is undefined. If the searched key is not found undefined is returned.

Code to search for a value

search(item, node) {
  if(node === undefined){
    node = this.root;
  }
  if(node.item === undefined){
    return false;
  }

  if(item > node.item){
    if(!node.right){
      return false;
    } else {
      return this.search(item, node.right);
    }
  } else if(item < node.item){
    if(!node.left){
      return false;
    } else {
      return this.search(item, node.left);
    }
  } else {
    return true;
  }
}

Deletion

Deletion causes the BST representation to change dynamically. The data structure must be modified in such a way that the properties of BST continue to hold.

Deletion of a leaf node

the parent node's pointer to leaf node gets replaced with undefined and consequently leaf nofe gets removed from the tree. Let's delete 7 from the above BST.

Deletion of a node that is not a leaf

Current node is replaced with a leaf node and leaf node is deleted. Let's delete 3 from the above BST. 3 is replaced with right most leaf node in its left subtree i.e., 1. Leaf node is deleted.

Code to delete a value

delete(item, node){
  if(node === undefined) {
    node = this.root;
  }
  if(node.item === undefined){
    return false;
  }

  if(node.item === item){
    let leafNode;
    if(node.left){
      leafNode = this.getRightMostItemOfSubTree(node.left);
      const temp = leafNode.item;
      leafNode.item = node.item;
      node.item = temp;
    } else if (node.right){
      leafNode = this.getLefttMostItemOfSubTree(node.right);
      const temp = leafNode.item;
      leafNode.item = node.item;
      node.item = temp;
    } else {
      leafNode = node;
    }

    if(leafNode.parent.left === leafNode){
      leafNode.parent.left = undefined;
    }
    else if(leafNode.parent.right === leafNode){
      leafNode.parent.right = undefined;
    }
    leafNode.parent = undefined;
    return true;
  }else if(item > node.item){
    if(!node.right){
      return false;
    } else {
      return this.delete(item, node.right);
    }
  } else if(item < node.item){
    if(!node.left){
      return false;
    } else {
      return this.delete(item, node.left);
    }
  }
}

Find Maximum

The maximum value in a tree will always exist at rightmost node of the tree

Code to find maximum value

findMax(){
  if(!this.root.right){
    return this.root.item;
  }
  return this.getRightMostItemOfSubTree(this.root).item;
}

getRightMostItemOfSubTree(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  if(!treeNode.right){
    return treeNode;
  }
  
  let currentNode = treeNode;
  while(currentNode.right){
    currentNode = currentNode.right;
  }
  return currentNode;
}

Find Minimum

The minimum value in a tree will always exist at leftmost node of the tree

Code to find minimum value

findMin(){
  if(!this.root.left){
    return this.root.item;
  }
  return this.getLeftMostItemOfSubTree(this.root).item;
}

getLeftMostItemOfSubTree(treeNode){
  if(!treeNode) {
    treeNode = this.root;
  }
  if(!treeNode.left){
    return treeNode;
  }
  let currentNode = treeNode;
  while(currentNode.left){
    currentNode = currentNode.left;
  }
  return currentNode;
}