Building Binary Tree

Data Structures in JavaScript

Photo by niko photos on Unsplash

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.

Figure 1: Sample Binary Tree

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.

Figure 2: Node Class

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.

Figure 3: Base BinaryTree Class

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.

Figure 4: BinaryTree Class Add Function

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.

Figure 5: BinaryTree Class AddNode Function

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.

Figure 6: BinaryTree Class Remove Function

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.

Figure 7: BinaryTree Class RemoveNode Function

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.

Figure 8: BinaryTree Class FindMinNode Function

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.