Navigating A Binary Search Tree

In a previous blog, I went over a coding challenge where we were searching for the closest value in a binary search tree (BST). But now we will go through a binary search tree and see how we can insert and search from a tree.

To start off lets explain the properties of a binary search tree. We start at the root, where the root node or parent node will have two children, a left node with a value and right node with a value. After the root parent and child nodes, the remainder of the tree may or may not have both a left and a right. The value of the left node is always going to be less than the value of parent, and the value of the right node is always going to be greater than the value of the parent. By knowing this, if you are inserting, searching or deleting a node, you immediately know which side of the tree you will be going through.

Searching

When you are searching for a value in a binary tree, you compare your target value with your root node. If the target value is greater than the root note, then you eliminate the left side of the tree, and go down the right side. If the target value is less than the root note, then you do the vice versa. Then you continue down the tree to the continuing nodes until you either find the value or return false if the value is not in the tree.

Using our tree at the top, lets try to search for the number 28. Immediately we will compare it to our root node, see that the left side can be eliminated and our search will continue down the right side. When we get the the child node with the value of 36, we will eliminate the right side and navigate down the left node. With our eyes, we can see that 28 is present. Seeing that the tree is sorted, you can always eliminate half of the tree or subtree on each level.

Lets say we are constructing a Binary Search Tree (BST) class and creating a method for search using contains. Below is how we would could write the method for contains to search fo the value.

Inserting

When we are inserting, we will initially use the search method then when we are at the correct position/node we add the value to the tree. Once again, we will compare the insert value to the root node to determine which side of the tree we can eliminate and which side we will traverse. Lets continue using the BST above and lets add a node with a value of 21. We can immediate eliminate the right side of the tree and traverse down the left side since our value is less than 25. We continue on until we stop at the node with the value 22. Since 21 is still less, we will create a left child node for the node with value of 22.

If we are were to create a method of inserting of a value, this is how the code would look like below:

There are just the start of the binary search tree. I encourage you to continue learning about the binary tree and dive in to others methods such as inverting a tree.