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

# Implement a Binary Search Tree

## Course launching November 17, 2020

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