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

Implement a Binary Search Tree

Course launching August 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! 🤓

Building a binary search tree is an excellent exercise to under stand 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 wont enforce it through balancing.

We will use a binary tree node that uses 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) {
      // Traverse left
      if(!currentNode.left) {
        currentNode.left = node;
        return this;
      }
      currentNode = currentNode.left;
    } else {
      // Traverse right
      if(!currentNode.right) {
        currentNode.right = node;
        return this;
      }
      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) {
        // Traverse left
        if(!currentNode.left) {
          currentNode.left = node;
          return this;
        }
        currentNode = currentNode.left;
      } else {
        // Traverse right
        if(!currentNode.right) {
          currentNode.right = node;
          return this;
        }
        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

Table of Contents