Implement a Binary Search Tree Coding Interview Question | Skilled.dev
Interview Question

Implement a Binary Search Tree

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

Building a binary search tree is an excellent exercise to understand how navigate trees and feel comfortable using them in interviews. Our tree will contain and insert and search method. We will assume they can operate in O(log n) time, but we won't enforce it through balancing.

We will use a binary tree node that has the following implementation:

class BinaryNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

And we will have a tree implementation which maintains our root node, and will add the ability insert and search for nodes.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    // Insert a node
  }

  search(data) {
    // Find a node in the tree
  }
}

insert(data)

To insert a node, we'll pass the data that we want it to store. If it is the first node inserted (the root doesn't exist), then we set this value to the root.

We begin to traverse the tree to the left or right. If the data we want to insert is less than the current node, we go left. If the data we want to insert is greater than the current node, we go right. If we hit a null, we insert the value there.

insert(data) {
  const node = new BinaryNode(data);

  // First insert becomes root
  if (this.root === null) {
    this.root = node;
    return this;
  }

  let currentNode = this.root;

  while(true) {
    if(data < currentNode.data) {
      // Insert the node if you reach a leaf and return
      if(!currentNode.left) {
        currentNode.left = node;
        return this;
      }

      // Continue by traversing left
      currentNode = currentNode.left;
    } else {
      // Insert the node if you reach a leaf and return
      if(!currentNode.right) {
        currentNode.right = node;
        return this;
      }

      // Continue by traversing left
      currentNode = currentNode.right;
    }
  }
}

search(data)

This method will return a node if we find its value in the binary tree, or otherwise it returns null. We traverse throught he left and right nodes by comparing the value we're looking for to the value of the current node.

search(data) {
  if (!this.root) {
    return null;
  }

  let currentNode = this.root;

  while(currentNode) {
    if(data < currentNode.data) {
      currentNode = currentNode.left;
    } else if(data > currentNode.data) {
      currentNode = currentNode.right;
    } else if (currentNode.data === data) {
      return currentNode;
    }
  }

  return null;
}

Complete Binary Search Tree Implementation

Here is our complete binary search tree. You can also interact with the code in a REPL.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const node = new BinaryNode(data);

    // First insert becomes root
    if (this.root === null) {
      this.root = node;
      return this;
    }

    let currentNode = this.root;

    while(true) {
      if(data < currentNode.data) {
        // Insert the node if you reach a leaf and return
        if(!currentNode.left) {
          currentNode.left = node;
          return this;
        }

        // Continue by traversing left
        currentNode = currentNode.left;
      } else {
        // Insert the node if you reach a leaf and return
        if(!currentNode.right) {
          currentNode.right = node;
          return this;
        }

        // Continue by traversing left
        currentNode = currentNode.right;
      }
    }
  }

  search(data) {
    if (!this.root) {
      return null;
    }

    let currentNode = this.root;

    while(currentNode) {
      if(data < currentNode.data) {
        currentNode = currentNode.left;
      } else if(data > currentNode.data) {
        currentNode = currentNode.right;
      } else if (currentNode.data === data) {
        return currentNode;
      }
    }

    return null;
  }
}
Prev
Binary Search Trees
Next
Binary Tree Max Depth
Loading...

Table of Contents