Coding Interview Prep: How to find a value in a Binary Search Tree in Javascript

Introduction

Let’s say we want to search for the number X.

1. We start at the root.
2. Then we compare the value to be searched with the value of the root.
3. If it’s equal, we are done.
4. If it’s smaller, we need to go through the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree is bigger.
5. Repeat the above step until there is no more traversal possible
6. If at any iteration, the key is found, then return true. Else return false.

Solution in Javascript

function search(root, key){
  //Base case: root is null or key is present at the root
  if (root == null || root.key == key){
    return root;
  }

  //key is greater than the root's key
  if (root.key < key){
    return search(root.right, key);
  }

  //key is less than the root's key
  return search(root.left, key);

}

//key to be found
let key = 6;

if (search(root, key) == null){
  console.log("key is not found!")
} else {
  console.log("key is found!");
}

Complexity

• The time complexity is O(h) where h is the height of the BST.
• The auxiliary space is O(h) where h is the height of the BST. This is because the maximum amount of space needed to store the recursion stack would be h.