Search in Binary Search Tree

This is how we search for an element in a Binary Search Tree.

First, we will check if there are any nodes in a Binary Search Tree. We will simply do it by checking if the root node exits. If the root node doesn’t exist, we will simply return from the function.

// check if the tree exist
   if(!this.root) {
     return false;
   }

If there is the root node, we will create a currentNode variable and assign the value of root to it.

let currentNode = this.root;

We will then, loop till we have currentNode.

If the value we are searching for is less than the value of currentNode, we will update the value of currentNodeand assign the left child to it.

if(value < currentNode.value) {
    currentNode =  currentNode.left;
}

If the value we are searching for is greater than the value of currentNode. We will update currentNode and assign its right child to it.

else if (value > currentNode.value) {
    currentNode = currentNode.right;
}

If the value we are searching for and the value of the currentNode is the same, we will simply return the currentNode.

else if(value === currentNode.value) {
        console.log(currentNode);
        return currentNode;
}

If we didn’t find the value, we will return false.

console.log(value + " not found");
    return false;
}

Here’s how complete lookup function look like:

lookup(value) {
   
   // check if the tree exist 
   if(!this.root) {
     return false;
   }
let currentNode = this.root;
    // loop till the currentnode 
    while(currentNode) {
      // check if value is less than currentNode
      if(value < currentNode.value) {
        currentNode =  currentNode.left;
      }
      else if (value > currentNode.value) {
        currentNode = currentNode.right;
      }
      else if(value === currentNode.value) {
        console.log(currentNode);
        return currentNode;
      }
    }
    console.log(value + " not found");
    return false;
  }

Here’ how the complete code looks like:

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
// create a class that implements binary tree
class BinarySearchTree {
  // start with empty bst
  constructor() {
    this.root = null;
  }
// insert value in bst
  // keep the rules of bst in mind
  insert(value) {
    // a node to insert
    const newNode = new Node(value);
// check if bst is empty
    // check if the root node is empty
    if (this.root === null) {
      // set new node as root node
      this.root = newNode;
    }
// if root node is not empty
    else {
      // assign the value of rootnode to a variable (to traverse)
      let currentNode = this.root;
      // loop till we find a place for newNode
      while (true) {
        // check if the value is less than root node
        if (value < currentNode.value) {
          // check if the left child(node) of the current node is null (doesn't exist) {
          if (!currentNode.left) {
            // set newNode as left
            currentNode.left = newNode;
            // get out of the loop
            return this;
          }
          // if there is left child set the value of left node to the current node
          currentNode = currentNode.left;
        } else {
          // check if the right node is empty
          if (!currentNode.right) {
            currentNode.right = newNode;
            return this;
          }
          currentNode = currentNode.right;
        }
      }
    }
  }
   lookup(value) {
   
   // check if the tree exist 
   if(!this.root) {
     return false;
   }
let currentNode = this.root;
    // loop till the currentnode 
    while(currentNode) {
      // check if value is less than currentNode
      if(value < currentNode.value) {
        currentNode =  currentNode.left;
      }
      else if (value > currentNode.value) {
        currentNode = currentNode.right;
      }
      else if(value === currentNode.value) {
        console.log(currentNode);
        return currentNode;
      }
    }
    console.log(value + " not found");
    return false;
  }
}
const bst = new BinarySearchTree();
bst.insert(99);
bst.insert (11);
bst.insert(9);
bst.insert(111);
bst.insert(222);
bst.lookup(222);
bst.lookup(111);
bst.lookup(5);

Output

Node { value: 222, left: null, right: null }
Node {
value: 111,
left: null,
right: Node { value: 222, left: null, right: null }
}
5 not found