Understanding Binary Search Tree

Greeting fellow coder.

On this installment I will break down the Binary tree data structure...you will learn about the fundamentals, how they work, how to traverse/ walk through a tree, and ask the question... are they OVERRATED? spoiler...they're not.

What is A Binary Tree ?

First, it is one of the many data structure used to efficiently map keys to values, for efficient search/retrieval, insertion, and/or removals.

A binary tree in particular has ONE root, that root has 2 child nodes, those 2 child nodes has 2 child nodes each, and eventually reach the leaves which are the last nodes that doesn't have any child node. If that didn't make a lot of sense check out an example picture of a binary tree below.

1. 8 is the root ( there should only be one root)
2. 4 is the left child node, and 12 is the right child node
3. 4 and 8 both has 2 child nodes, and so on.
4. 1,3,5,7,9,11,13,15 are all leaves.
5. It is called a binary tree because every node can have no more than 2 child node. (it is possible to have one child node, that just means the other child node is NULL)

How do you use it?

The binary tree above is also a perfect example of a Binary Search Tree, which states every child node left of the root must be less than the root node, and every child node to the right of the root must be higher.

This ordering property enable us to search through the tree quickly.
lets take a look at another tree, and this time lets search for the number 83

Steps:

1. We see that the root(84) is greater than 83 therefore we can cut out all of the child nodes from the right.
2. That leaves us to 54 the left child node of the root, from there we see that 83 is higher than 54 so we will go to its right child node 73.
3. 73 left child is null, but its right child is 83! the number we wanted to search.

Now lets say we want to insert the number 90. The steps would be similar to search.

Steps:

1. 90 is higher than the root so we will go to the right to 87.
2. 90 is still higher than 87 so we will go right of node 87 to 94.
3. 90 is less that 94 so we will go to the left, where it is null.
4. Since it is null this is where we will insert 90. Check below for results

Removing a node in a tree is a little more complex. Let me show you.

Lets take a look at this new binary search tree.

Lets say I want to remove 13.

Steps:

1. Starting from the root(89) which 13 is less than, so we move to the left child node which is 13.
2. From there the function will ask if 13 is a leaf, which it is not.
3. So it will go to the right, at 34 and ask if 34 is a leaf which it's not.
4. Since 13 is less than 34 we will now move to the left child node of 34, 21.
5. It will ask if 21 is a leaf, which it's not.
6. Since 13 is less than 21, we will move to the left child node again at 20.
7. Again at 20, we know it is not a leaf so we will move to the left child node to 14
8. At 14 they will ask it if this node is a leaf, the answer is yes.
9. Now the function will replace 13 with its "successor" 14. Results below

Lets Traverse!

We just went through how to search, insert, and remove nodes from a binary tree. Lets now see how we can traverse one.

There are 3 methods to traverse through a binary tree:

1. Inorder
   In simple term we will go from left node, to root, than to right node.

2. Preorder
   In simple term we will go from root, to left node, than to right node.

3. Postorder
   In simple term we will go from left node, to right node, than root.

*Typically Inorder traversal is most common because it allows the nodes to be printed in order. *

lets take a look at this tree for example:

The Inorder traversal steps are:

A. start from the root(75) and move toward the left node 3, then we can ask does 3 have a child left node? since 3 doesn't have a child left node. We will log 3 and move on to its right child node 7.

(3)
B. Does 7 have a child left node? No, we will now log 7, and move on to it's right child node 24.

(3,7)
C. Does 24 have a left child node? Yes, it is number 8. Now we ask if 8 have a left child node ? No, we will log 8.

(3,7,8)
D. We will move back to 24 and log 24, because its child node 8 have already been logged, then move on to it's right child node 59.

(3,7,8,24)
E. Does 59 have a left child node? No, so we will now log 59. Then traverse back to the root.

(3,7,8,24,59)

F. Because we've register all of the left child nodes of the root. We can now log 75.

(3,7,8,24,59,75)

G. Now we move on to the right of the root node to 95. And ask does it have a left child node? Yes, now to move to 91. Does 91 have a left child node? No, we can now log 91.

(3,7,8,24,59,75,91)

H. Because we've register all of the left child nodes of 95. We can now log 95.

(3,7,8,24,59,75,91,95)

I. Then we can move on to 95 right child node 99. And ask, does 99 have a left child node? No, we can now log 99.

(3,7,8,24,59,75,91,95, 99)

By using Inorder traversal through this Binary Tree, you can see it the nodes are printed in order. I will not go over Preorder or Postorder on this article but you can check out these easy to understand videos from Michael Sambol below using those 2 methods.

Preorder: https://youtu.be/1WxLM2hwL-U
Postorder: https://www.youtube.com/watch?v=4zVdfkpcT6U

Why do you need to know Binary Search Tree ?

Binary search trees are collections that can efficiently maintain a dynamically changing data set in sorted order. Having a sorted array is useful for many tasks because it enables binary search to be used, to efficiently locate elements.

In terms of Big O notation, the average time to search, insert, and delete data is Θ(log(n)).

Who knows, you might be ask about binary search tree and how to traverse on in a interview.

hopefully this article was helpful.

Thanks for reading me !

Comments

[Sumeet M]

Really helpful. 🙌🏻

I also recommend others to go through this tutorial. It contains example programs of binary search tree in c, c++, java & python.