# Building Binary Tree

## Data Structures in JavaScript

A binary tree is a specific type of graph data structure and is often the first graph people learn. Binary trees contain a root node that has two branches which are arranged from left to right in ascending order. Each branched node can have up to two branches of its own, and so on. If these two requirements are not met then the data structure is likely still a tree, just not a binary tree. For instance, if a node had three branches it might be considered a ternary tree. This article will cover only binary trees as they are a good stepping stone to learning trees. It is also noted assumed that a tree will not contain repeated data. Let’s start with a diagram which demonstrates the previously state requirements.

## Node Class

Based on Figure 1 a simple `Node`

class can be constructed with a `data`

property as well as a `left`

and `right`

property that point to the child nodes. The left and right properties should default to `null`

as they might not be known when an instance of the `Node`

class is instantiated.

## Binary Tree Class

From this point we can define a `BinaryTree`

class which will hold all the related functions such as adding and removing nodes. When a `BinaryTree`

instance is instantiated it should also contain a `root`

property that points to the root `Node`

. The `root`

can be updated as the `BinaryTree`

is populated.

## Add Function

With the constructor of the BinaryTree class defined we can add the first function, `add`

which inserts a new node in the correct location in the tree. The correct place being ascending order from left to right.

In Figure 4, a new Node is instantiated and then assigned to the `root`

property of `BinaryTree`

if the `root`

is currently `null`

, otherwise the new `Node`

is passed to the helper function `addNode`

. This helper function will step through the appropriate branches of the tree to find the correct location as seen in Figure 5.

It is seen in the above code snippet that as the function looks at the `left`

and `right`

properties of the passed in `node`

, it will call itself recursively if that property is not `null`

. This is because a Node is already defined in that position so the function must step down another level in the tree. This continues until an empty spot is found to place the `newNode`

. Note that this function assumes that `node`

is a instance of `Node`

.

## Remove Function

Now that we have successfully implemented methodology to add Node instances to the BinaryTree, the logical next function is `remove`

. This is a little more complicated than `add`

as there are a few cases that need to be handled; removing a `Node`

with empty `left`

and `right`

properties, a `Node`

with only one of those properties empty, and one with both `left`

and `right`

populated. This function will also have to step from the `root`

of the tree and search for the appropriate data so a recursive solution makes sense.

In the `remove`

function the `root`

property is updated as removing a `Node`

will update the entire tree. From here the helper function `removeNode`

is called to step through the tree to find the data before removing that `Node`

.

The first half of figure 7 shows how `removeNode`

recursively steps through the tree until the correct `Node`

is located. There is a special case where a `null`

`Node`

is found which indicates the data does not exist in the tree. From here `removeNode`

checks the children of the selected `Node`

to determine how to remove it. If there is no children then no additional work is required but if there is one child that child must replace the selected `Node`

.

The final case of the selected `Node`

having two children is handled at the end of the `removeNode`

. The left side of the selected node is kept the same but the right side is manipulated. The minimum `Node`

of the right side is pulled up to replace the selected `Node`

data with the help of function `findMinNode`

. That `minimum`

Node is then removed via a recursive call to `removeNode`

.

## Summary

You have now completed the construction of a Binary Tree. This special type of graph has a `root`

`Node`

which has up to tow children nodes which themselves can have up to two children, and so on. The data is arranged in ascending order from left to right as shown in Figure 1. Adding a `Node`

was relatively straightforward but removing a node required checking the children of the existing `Node`

. Take some time to ensure you understand how `removeNode`

is manipulating the `BinaryTree`

.