Create A Binary Search Tree

How to create a binary search tree from an array

Image for post
Image for post

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 (BST):

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.

Image for post
Image for post
Unsorted Integer Array

The first value in the array is 7, so the first step in constructing the tree will be to make 7 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 2 to the tree will be to compare it to the root node:

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

Image for post
Image for post

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

Image for post
Image for post

Making our way through the array we come to the 1. We’ll start with comparing the array to 7, which it’s less than. So we move to the left and compare it with 2, it’s less than 2 and 2 doesn’t have any children to the left, so we make 1 the left child of 2.

Image for post
Image for post

Continue making our way through the array we come to the 5. We’ll start with comparing the array to 7, which it’s less than. So we move to the left and compare it with 2, it’s greater than 2 and 2 doesn’t have any children to the right, so we make 5 the right child of 2.

Image for post
Image for post

Lastly we will insert the value 14. We’ll start with comparing the array to 7, which it’s greater than. So we move to the right and compare it with 9, it’s greater than 9 and 9 doesn’t have any children to the right, so we make 14 the right child of 9.

Image for post
Image for post

We are done creating our Binary Search Tree (BST). 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. An example of this is a AVL tree.

You can watch a playlist on Binary Search Trees here, or watch the playlist below:

Video Playlist On Binary Search Trees

If you are also interested in reading up a little bit more on Binary Search Trees and other data structures & algorithms, then I strongly recommend you check out the amazing book Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition. This book goes over topics like binary search trees, sorting algorithms, heap sort, hash tables, red and black trees, divide and conquer algorithms, greedy algorithms and the list goes on !

Image for post
Image for post
Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, data structures, discrete mathematics and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store