When it comes to developer job interviews, questions regarding data structures are very popular and are therefore important to prepare for.Binary search trees are one of my favorite data structures to work with because they’re incredibly efficient, if managed properly, and they are also straightforward to understand.

Let’s begin by first establishing some rules for Binary Search Trees:

1. A parent node has, at most, 2 child nodes.
2. The left child node is always less than the parent node.
3. The right child node is always greater than or equal to the parent node.

Here is the array that we’ll be using for this tutorial:

This is a basic integer array consisting of seven values that are in unsorted order.

Create a Binary Search Tree

The first value in the array is 10, so the first step in constructing the tree will be to make 10 the root node, as shown here:

With the root node set, all of the remaining values will be children of this node. Referencing our rules from the beginning of this post we know the child nodes will be designated as the right or left child nodes depending on their value. Therefore the first step we’ll take for adding the 7 to the tree will be to compare it to the root node:

If the 7 is less than the 10, it will become the left child node. If the 7 is greater than or equal to 10 it will move to the right. Since we know that the 7 is less than 10 we designate it as the left child node, as shown here.

Recursively Perform Comparisons for Each Element

Following the same pattern, we perform the same comparison with the 14 value in the array. Comparing the value of 14 to the root node of 10 we know that 14 is the right child.

Making our way through the array we come to the 20. We’ll start with comparing the array to 10, which it’s greater than. So we move to the right and compare it with 14, it’s greater than 14 and 14 doesn’t have any children to the right, so we make 20 the right child of 14.

Our tree is coming along nicely. Now we have the value 1. Following the same pattern as the other values we will compare 1 to 10, move to the left and compare it with 7, and finally make 1 the left child of the 7 node.

With the 5 value we compare it to the 10. Since 5 is less than 10 we traverse to the left and compare it with 7. Since we know that 5 is less than 7 we continue down the tree and compare 5 to the 1 value. With 1 having no child nodes and 5 being greater than 1 we know to make 5 the right child of the 1 node.

Lastly we will insert the value 8 into the tree. With 8 being less than 10 we move it to the left and compare it with 7. 8 is greater than 7, so we move it to the right and complete the tree making 8 the right child of 7.

I hope that you can appreciate the simple elegance of binary search trees. Like so many topics in programming and in life, the strength of binary search trees comes from their ability to allow data to be broken into small, connected components. From which point we can work with the full data set in an organized manner. In referencing the binary search tree tutorial I gave previously, we could take the tree that we constructed in this guide and efficiently search through it to find any element that had previously been in the array.

Potential Issues with Binary Search Trees

As great as binary search trees are, there are a few caveats to keep in mind.

Binary search trees are typically only efficient if they are balanced. A bal­anced tree is a tree where the dif­fer­ence between the heights of sub-trees of any node in the tree is not greater than one. If that didn’t make sense, here’s an example that may help. Imagine that our array had started out as being sorted. With a sorted array our binary search tree would look something like this.

If we tried to run the binary search tree algorithm on this tree it would perform exactly the same as if we simply iterated over the array until we found the value we were searching for. The strength of binary search comes from being able to quickly filter out the unnecessary values. When a tree is unbalanced, especially like the type of tree that would result from a sorted array, it won’t yield the same benefits as a balanced tree. You can compare it back to the final output that our unsorted array generated here.

All this means is that it’s vital to understand the data that you’re working with when you’re creating a binary search tree. You can integrate subroutines, such as randomizing an array before you create a binary search tree to balance it. In the future I’ll also cover topics related to AVL and Red Black trees. These types of algorithms ensure that a tree is maintains the proper balance characteristics.

I hope that this has been a helpful guide to understanding how to practically create a binary search tree from an array data structure. Good luck with the interview!