Binary Search Trees

How to create a binary search tree from an array

I’m going to discuss how to create a binary search tree from an array. This will be a basic integer array that contains 6 values that are unsorted.

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.

Unsorted Integer Array

The first value in the array is ‘7’, so it will be the root node in the tree. With the root node set, all of the remaining values will be children of this node. Using our rules from the beginning of this article we know the child nodes will be designated as the right or left child nodes depending on their value.

Next we insert the next value in the array. First we need to compare it with the parent node ‘7’. Since the next value is ‘2’ and ‘2’ is less than ‘7’ (it’s parent), then ‘2’ will go to the left of the node.

Insert the next value from the array into the tree, the value containing ‘9’. Compare the value with it’s parent node (the node containing the value ‘7’). Since ‘9’ is greater or equal to ‘7’, it will go to the right of its parent node.

Next insert the value ‘1’ in the tree. Since ‘1’ is less than ‘7’ (the root node), it will go to the left of that node. Next we need to compare the node that contains the value ‘2’ with our current value ‘1’. Since ‘1’ is less than ‘2’, it will be placed to the left of ‘2’. The node containing the value ‘2’ is its parent.