Binary Search Tree Data Structure — Overview

There are many data structures. For example, Linked List, Graph, Hash, etc. In this article, I will elaborate on one of the popular data structures, which is the Binary Search Tree (BST). When we interact with array, we will do similar functions such as sorting, searching, inserting, and removing. There are so many ways and algorithms with different effectiveness and complexity. For example, we will use quick sort for sorting an array, and use binary search for searching an index of the wanted array item. With a binary search tree, we will make algorithms more structured, time-friendly, and space-friendly.

Left and Right

As the name implies “binary”, we will interact with YES or NO, 1 or 0, and TRUE and FALSE. In the binary search tree, we will interact with LEFT and RIGHT. If the inserted value is greater than the root, the value will be placed on the right side of the root. If smaller than the root, the value will be stored on the left side.

For example, we have [40, 30, 50, 25, 35, 45, 60]. How to convert it to BST? The way is simple, check it out!

• 40 is the root.
• 30 is smaller than the root (40), place it on the left side.
• 50 is greater than the root (40), place it on the right side.
• 25 is smaller than the root (40), and there is a child (30) on the left side. 25 is smaller than 30, place it on the left side of 30.
• 35 is smaller than the root (40), and there is a child (30) on the left side. 35 is greater than 30, place it on the right side of 30.
• 45 is greater than the root (40), and there is a child (50) on the right side. 45 is smaller than 50, place it on the left side of 50.
• 60 is greater than the root (40), and there is a child (50) on the right side. 60 is greater than 50, place it on the right side of 50.

You can call the subtrees as root, 30 is the root of 25 and 35 and 50 is the root of 45 and 60. 25, 35, 45, and 60 aren’t root because they don’t have children.

Let’s code!

Given an array [30, 20, 40], we will change it to Binary Search Tree. Remember the logic! You need to focus on ROOT, LEFT, and RIGHT.

This is the result!