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:

  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

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

Insert the next value from the array, the value containing the number ‘5’. Compare ‘5’ with the value of the root node ‘7’. Since ‘5’ is less than ‘7’ it will go to the left of that node. Next we compare the ‘5’ with the node that contains the value ‘2’. Since ‘5’ is greater than or equal to ‘2’, it will go to the right of the node containing the value ‘2’. The node containing the value ‘2’ is its parent.

Image for post
Image for post

Finally we add the last value ‘14’ from the array into our Binary Search Tree. First we compare this value with the value in our root node. Since ‘14’ is greater than or equal to ‘7’, we will go to the right of out root node. Next we need to compare the node that contains the value ‘9’ with ‘14’. Since ‘14’ is greater than or equal to ‘9’, it will go to the right of that node. The node containing the value ‘9’ will be its parent.

Image for post
Image for post

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

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

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

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Recurrence Relation:

Image for post
Image for post

RESOURCES:
https://www.crondose.com/2016/06/create-a-binary-search-tree-array/

Image for post
Image for post

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