What is a binary search tree?

This is part one of a two-part blog series. In the first blog, we’ll go over what a tree is and the rules that make a tree a binary tree. In the second blog, we’ll go over how to find or add nodes in a binary tree.

Trees

The tree data structure works the same way a family tree works. This is because the nodes inside the tree are connected in a parent -> child relationship. The parent nodes have pointers to all of their children. An example of a tree will be left down below.

In this example “Grandma” is the root node. Root nodes are the only nodes that don’t have parents. The “Mom” node is the child node of the “Grandma” node and the parent node for child 1, 2, and 3. This makes the “Mom” node a branch in the tree because it has a parent and has children. Child nodes 1, 2, and 3 are all children of “Mom” but have no children of their own so they are the leaves of the tree.

Binary Search Trees

Now that we have a good understanding of what a tree is let’s get into binary trees. This section Is going to go over the rules that make a tree into a binary search tree.

A Binary search tree only has two rules to follow:

• Rule 1 No parent can have more than two children
• Rule 2 the left child node must be less than it’s the parent node, and each right child has to be more than the parent node.

So given a list of numbers 1,2,3,4,5,6,7 our tree would look like this:

The first number is one so it’s the root next is two so we ask if two bigger or smaller than one. Since two is bigger it goes to the right child. Next, is three bigger than one? Yes, so we go to the right again but this time there is already a node there so we ask if three is bigger than two. Since three is bigger than 2 it goes to the right child of 2 this continues till the list is over.

Now if we had a random list of numbers it might look different say the numbers are in this order 3,1,4,2,6,7,5 the list would look like this:

I used the same rules as I mentioned earlier but this time the list of numbers didn’t just keep getting bigger. You didn’t know if the next number was greater or less than the previous number.

Next week we’ll be going over how you can add and find things in a binary search tree. Now we should know how to structure both trees and binary trees. I hope you found this blog helpful in any way.