Binary Tree
A tree is a data structure that allows for storing data in a non linear fashion. Arrays and Linked Lists are used to store data linearly. Trees that you might be familiar with are file systems, such as what you see when you open Windows Explorer; HTML is a prime example of a tree structure, you have tags nested within tags. We will explore the properties as well as a simple JavaScript implementation of the Binary Tree (BT).
A Binary Tree is a specific type of tree. The rules it must adhere to maintain its classification are as follows. Let’s say we have one node, to be a node in this structure, it should have the following properties: a value, a left property, and a right property. This node would be a parent to the left and right properties. Left and right properties would point to other nodes whom would be the children of this parent node. To be a binary tree means that the parent can have at most up to two children, hence the term binary.
If we imagine a real life tree which is inverted, meaning the roots are now the top of the tree and the branches flow from the root, it is analogous to our representation below. The root is our topmost node, all of its children to the left must be smaller than the value of the root node, whereas all the children to the right must be of a larger value than the root node. Each consecutive child is a parent to its children nodes and the same rule that applies to the root node apply to its children nodes. In other words, if a node is a parent then its larger value children will be found to the right, and its lower value children to the left.
With that background we will go on to implement a BT which will consist of a Node class and a Binary Tree class that has a pointer to the root. We should be able to add a node to this tree, and we should be able to search for a value of a node within the tree. We have four cases to consider when implementing the tree.
The first case is when the BT is empty, in order for us to add a node we simply add it, and point the BT class to this node as the root.
The second case is when the value of the node we’re trying to add already exists within the tree, in our case to keep our code base simple we will not add it and return undefined.
The third case is when value of the node is less than the root node, we will proceed to the left child of this node and repeat the comparing steps until we find the proper place to settle the node in.
The fourth case is when the node’s value is larger than the root, we will proceed to the right child, and repeat the comparing steps until the node is settled into its rightful place.
The implementation of finding a value within our BT will be similar to the steps we’ve used above, but we’ll use recursion to traverse our tree until the value is found.
Feel free to give this a try in your favorite editor.