Binary search tree is very efficient and has strengths of array and linked list.
Array and Linked List are great data structure but they have some weaknesses.
It’s fast to access array but slow to adjust the size.
It’s slow to access linked list but fast to adjust the size.
However, it’s fast to access binary search tree and it’s still very flexible to adjust the size.
What is Binary Tree?
Before diving into binary search tree we need to understand binary tree first.
Binary tree is an extended form of singly linked list but has two pointers to other nodes (children) instead.
Pointers are not to the previous and next but to left and right children.
Let’s first take a look at the picture of an example binary tree.
As you see the above, the topmost node is the root of the tree.
The root has two children node, left and right. (please note that you don’t have to call it left & right)
The right child node doesn’t have any child and thus it is called leaf node of the tree.
How is binary search tree different from binary tree?
The only difference between binary search tree and binary tree is the order of nodes when a node is inserted.
Binary search tree always forces the rule below.
- Any value less than the value of the current node is always placed on the left child leaf node.
- Any value greater than the value of the current node is always placed on the right child leaf node.
- Move to proper child node if either child node is already created (non-leaf).
Let’s take a look at the example below for insertion.
I am going to insert 5 nodes and let’s see how the insertion is done.
I first inserted a node with value 20 which became the root of the tree since the tree was empty.
Then I inserted another node with value 10 which is the left child of the root node because 10 is less than 20.
If I have another node with value 15 where will it be placed?
15 is less than 20 so it goes to the left child of the root node.
But the left child is already there so we compare 10 and 15.
15 is greater than 10 and the node with value 10 doesn’t have any right child.
Therefore, a node with value 15 will be the right child of the node with value 10. And it is a leaf node.
Please note that the node is always inserted as the leaf node of the tree.
I have two more nodes with values 8 and 21 respectively.
The node with value 8 will be the left child of the node with value 10.
The node with value 21 will be the right child of the node with value 20.
Performance of Binary Search Tree
As you see the above example binary search tree always maintains the order of nodes after the insertion.
This is great since it will be very fast to find and access a certain node thanks to its property.
Let’s take a look at how it will find a node with an example.
Let’s say I want to find the node with value 15.
First, it takes a look at the root node and finds out that 15 is less than its current value 20.
Therefore the node must exist somewhere on the left side of the root node.
It checks the node with value 10 and finds out that 15 is greater than 10.
Therefore the node must exist somewhere on the right side of the node with value 10.
Then, finally, the node with value 15 is found in the right child of the node with value 10.
Did you notice that we are eliminating half of the tree every time we compare which is very similar to binary search?
In fact, insertion and search and deletion are really the same as binary search and their performance is also the same – O(log n).
Insertion – O(log n)
Search – O(log n)
Deletion – O(log n)
Please note that the above performance is valid only if the tree is balanced which depends on the insertion order unless it balances automatically after every insertion.
In the worst-case scenario where the tree is extremely unbalanced and essentially becomes like a linked list all the operation cost will be O(n).
I won’t discuss how to balance the tree as it will be a lot of information for just one post.
Code Example
Here is the code example of binary search tree in C++
struct Tree
{
// This could be any data type
int val;
Tree *leftChild;
Tree *rightChild;
};
Tree *searchTree(Tree *elt, int searchVal)
{
// value not found in the tree
if (!elt)
{
return 0;
}
// found value
if (searchVal == elt->val)
{
return elt;
}
// search value must be in one of left children nodes
else if (searchVal < elt->val)
{
return searchTree(elt->leftChild, searchVal);
}
// search value must be in one of right children nodes
else
{
return searchTree(elt->rightChild, searchVal);
}
}
void insertTree(Tree **elt, int newVal)
{
// found correct place to insert
if (!*elt)
{
Tree *newNode = new Tree;
newNode->val = newVal;
newNode->leftChild = 0;
newNode->rightChild = 0;
*elt = newNode;
return;
}
Tree *node = *elt;
// new node must be inserted in one of left children
if (newVal <= node->val)
{
insertTree(&node->leftChild, newVal);
}
// new node must be inserted in one of right children
else
{
insertTree(&node->rightChild, newVal);
}
}
// example of inorder traversal. I am just printing here
// this is called inorder traversal.
// this will print above example tree as this.
// 8 10 15 20 21
void printInOrder(Tree *head)
{
if (!head)
{
return;
}
printInOrder(head->leftChild);
// you can do any operation here
cout << head->val << " ";
printInOrder(head->rightChild);
}
Conclusion
We have taken a look at binary search tree and how it maintains the order of nodes which enables fast operations such as insertion, search, and deletion.
It is a powerful data structure that has strengths of array – fast search – and linked list – flexible size adjustment.
However, the tree needs to be balanced in order to be efficient.
There is multiple tree balance logic and I will try to explain them in other posts.