Implement a Binary Search Tree | Skilled.dev
Interview Question

Implement a Binary Search Tree

Loading...

Building a binary search tree is an excellent exercise to understand how to navigate trees and feel comfortable using them in interviews. Our tree will contain an insert and search method. We will assume they can operate in O(log n) time, but we won't explicitly enforce this 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;
  }
}

We will use a tree implementation which maintains our root node, and we will add the logic to 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 call the method with the data that we want this item to hold. If it is the first node inserted (the root doesn't exist), then we set this value as the root.

If it's not the first node, 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 found the end of the path which is the location where this item should exist to be sorted correctly, and 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 right
      currentNode = currentNode.right;
    }
  }
}

search(data)

This method will return a node if we find its value in the BST, or otherwise it returns null. We traverse through the 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 right
        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;
  }
}
Loading...

Table of Contents