Understanding Binary Search Trees
Tags: javascript, datastructure, beginners, webdev
Published: 2020-07-17 22:29:16

As promised in my last post on [recursion](https://dev.to/christinamcmahon/recursion-explained-with-examples-4k1m), which I recommend reading before this article as we will be using it a lot in my examples, I want to take a closer look at the tree data structure in this article. **Trees** are a non-sequential data structure that is useful for storing information that needs to be found easily. In other words, they are an abstract model of a hierarchical structure (think of a family tree). Trees consist of **nodes** with a parent-child relationship. 

![example of binary tree with labelled parts](https://miro.medium.com/max/975/1*PWJiwTxRdQy8A_Y0hAv5Eg.png)

# Binary Tree and Binary Search Tree
A node in a **binary tree** has at most two children: a left and a right child. This definition allows you to write algorithms to insert, search, and delete nodes more efficiently. Refer to the image above to see a binary tree and the key vocabulary that I will be using in this article.

![example of binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/hor6r2ok5fshggx1apd6.png)

As you can probably guess, a **binary search tree (BST)** is a binary tree. The key difference is that a BST only allows you to store nodes with lesser value on the left side and nodes with greater value on the right. In case you didn’t notice, this is exemplified in the image above. If you’re having a difficult time understanding how the image is ordered, don’t worry, we’ll go into more detail in the next sections!

## Creating the Node and BST Classes
As usual, I highly encourage you to code along with me and to continuously test/play around with whatever we write. To start, we will create our `Node` class which will represent the nodes in our BST:
```javascript
class Node {
	constructor(data) {
		this.data = data; // node value
		this.left = null;	// left node child reference
		this.right = null; // right node child reference
	}
}
```
Next, we will declare the basic structure of our `BinarySearchTree` class:
```javascript
class BinarySearchTree {
	constructor() {
		this.root = null; // root of bst
	}
}
```
Our next step will be to implement some methods. Here’s what we’ll cover:
- `insert(data)`
- `inOrderTraverse()`
- `preOrderTraverse()`
- `postOrderTraverse()`
- `search(data)`
- `remove(data)`

## Inserting a Node into a BST
To insert a new node into a tree, there are two steps we will follow: 
1. **Verify whether the insertion is a special case.** In other words, we need to check if the node we are trying to add is the first one in a tree. If it is, we simply need to point the `root` to this new node by creating an instance of the `Node` class and assigning it to the `root` property. 
2. **Add the node to a different position than the `root`.** 

```javascript
insert(data) {
	let newNode = new Node(data);
	
	if(this.root === null) {
		this.root = newNode;
	} else {
		this.insertNode(this.root, newNode); // helper method below
	}
}

insertNode(node, newNode) {
	if(newNode.data < node.data) {
		if(node.left === null) {
			node.left = newNode;
		} else {
			this.insertNode(node.left, newNode);
		}
	} else {
		if(node.right === null) {
			node.right = newNode;
		} else {
			this.insertNode(node.right, newNode);
		}
	}
}
``` 
To summarize, `insert(data)` creates a new `Node` with a value of `data` and if the tree is empty, it sets that node as the tree’s `root`, otherwise it calls `insertNode(this.root, newNode)`. *insertNode(node, newNode)* is our helper method which is responsible for comparing the new node data with the data of the current node and moving left or right accordingly recursively until it finds a correct node with a null value where the new node can be added. 

As an example, if we were to execute the following code... 
```javascript
const BST = new BinarySearchTree();
BST.insert(11); // establishes root node 
BST.insert(7);
BST.insert(9);
BST.insert(15);
...
BST.insert(6);
```
...we can illustrate the last insert with this diagram:
![inserting 6 into binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/nv4bw81aq1laf58dgpfi.png)

## Traversing the BST
Traversing a tree is the process of visiting all the nodes in a tree and performing an operation at each node. The big question is, how should we go about this? There are three common approaches: in-order, pre-order, and post-order.

### In-Order Traversal
An **in-order traversal** will visit all nodes in ascending order, starting from a given node (optional), and perform the given callback function (also optional). Again, we will use recursion here:

```javascript
inOrderTraverse(node, callback) {
	if(node != null) {
		this.inOrderTraverse(node.left, callback);
        callback(node.data);
        this.inOrderTraverse(node.right, callback);
    }
}
```
The following diagram shows the path that our `inOrderTraverse` takes:

![in-order traversal of binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/qn6dtt7tccizpg76swp8.png)

### Pre-Order Traversal
A **pre-order traversal** visits the node prior to its descendants. Take note of the pretty subtle difference the the order in the code and in the diagram:

```javascript
preOrderTraverse(node, callback) {
    if(node != null) {
        callback(node.data);
        this.preOrderTraverse(node.left, callback);
        this.preOrderTraverse(node.right, callback);
    }
}
```

![pre-order traversal of binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/rrqqihedxk7svv3pntcj.png)

### Post-Order Traversal
If you haven't guessed already, a **post-order traversal** visits the node after its descendants. You can probably guess how the code will differ here but be sure to double check yourself with the diagram:
```javascript
postOrderTraverse(node, callback) {
    if(node != null) {
        this.postOrderTraverse(node.left, callback);
        this.postOrderTraverse(node.right, callback);
        callback(node.data);
    }
}
```
![post-order traversal of binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/mldxkzqjjqnfmuhwke2b.png)

## Searching for Values in a BST
In our implementation, `node` represents the current node and data represents the value we are searching for:
```javascript
search(node, data) {
    if(node === null) {
        return null;
    } else if(data < node.data) {
        return this.search(node.left, data);
    } else if(data > node.data) {
        return this.search(node.right, data);
    } else {
        return node;
    }
}
```
I encourage you to give test your code here and you can add in a console.log so you can see which nodes are visited. Even if you aren't coding along, go ahead and trace one of the diagrams in this article and predict the method's path when searching for a particular value. You'll notice how easy it is to find the max and min values too!

## Removing a Node from a BST
The `remove` method is the most complex method we will cover in this article. It's complexity is due to the different scenarios that we need to handle and because it is recursive. 

```javascript
remove(data) {
    this.root = this.removeNode(this.root, data); // helper method below
}

removeNode(node, data) {
    if(node === null) {
        return null;
    // if data to be deleted is less than the root's data, move to the left subtree
    } else if(data < node.data) {
        node.left = this.removeNode(node.left, data);
        return node;
    // if data to be deleted is greater than the root's data, move to the right subtree
    } else if(data > node.data) {
        node.right = this.removeNode(node.right, data);
        return node;
    // if data is similar to the root's data, delete the node
    } else {
        // delete node with no children (leaf node)
        if(node.left === null && node.right === null) {
            node = null;
            return node;
        }

        // delete node with one child
        if(node.left === null) {
            node = node.right;
            return node;
        } else if(node.right === null) {
            node = node.left;
            return node;
        }

        // delete node with two children
        // minimum node of the right subtree is stored in newNode
        let newNode = this.minNode(node.right);
        node.data = newNode.data;
        node.right = this.removeNode(node.right, newNode.data);
        return node;
    }
}
```
If we end up finding the matching node to be deleted, there are three scenarios to handle which we will discuss in more detail below. These scenarios can be found in the big else statement in the code. 

### Removing a Leaf Node
The first scenario involves a leaf node which does not have a left or right child. In this case, we will need to remove the node by assigning `null` to it. However, don't forget that we will also want to take care of the references from the parent node. Refer to the diagram which shows the removal of a leaf node:

![remove leaf node from binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/lecc6pb9z4rvdshken04.png)

### Removing a Node with One Child
The second scenario involves a node that has a left of right child. As you can see in the diagram below, we will need to skip matching node and assign the parent pointer to the child node: 

![remove node with left child in binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/25yp2yukyvixl7kwj10w.png)

### Removing a Node with Two Children
The third and final scenario involves a node with both let and right children. To remove such a node, follow these steps:

1. Once you find the node to be removed, find the minimum node from its right edge subtree (refer to shaded area in the diagram below).
2. Next you can update the value of the node with the key of the minimum node from its right subtree. With this action, you are replacing the key of thenode, which means it is effectively removed. 
3. Now you have two nodes in the tree with the same key which cannot happen (refer to the two 18s in the diagram). Thus, you need to remove the minimum node from the right subtree since you moved it to the place of the removed node. 
4. Finally, return the updated node reference to its parent. 

![remove node with two children from binary search tree](https://dev-to-uploads.s3.amazonaws.com/i/762p0nd25az409bowp6s.png)

## Conclusion
In this article, we covered the algorithms to add, search for, and remove nodes from a binary search tree as well as treee traversal. 

For some additional fun, I came across this interesting tool where you can play around with an [interactive BST](https://www.cs.usfca.edu/~galles/visualization/BST.html) along with many other data structures, created by David Galles. And if you want to learn more about the cover image and how it relates to binary trees, check out this explanation of [symmetric binary trees](https://larryriddle.agnesscott.org/ifs/pythagorean/symbinarytree.htm) by Larry Riddle (be warned it's pretty math heavy but there are some cool illustrations)!