- A binary tree is a non-linear data structure which is a collection of elements called nodes.
- In a binary tree, the topmost element is called the root-node. An element can have 0,1 at the most 2 child nodes.
- There are many variants of Binary tree. A Binary search tree or BST is one among them.
A binary search tree, also known as ordered binary tree is a binary tree wherein the nodes are arranged in a order. The order is :
a) All the values in the left sub-tree has a value less than that of the root node.
b) All the values in the right node has a value greater than the value of the root node.
c) The same rule is carried forward to all the sub-tree in tree.
Since the tree is already ordered, the time taken to carry out a search operation on the tree is greatly reduced as now we don’t have to traverse the entire tree, but at every sub-tree we get hint where to search next.
- Binary trees also help in speeding up the insertion and deletion operation.
- The average running time of a search operation is O(log2 n ) as at every step, the search-area is reduced by half.
Consider an example. We need to insert the following elements in a binary tree:
- Firstly we insert the first element as the root node.
- Then we take the next element in queue a check whether it is lesser or greater than root node.
- Here it will go to left tree as 2 is less than 48.
- Then the third value, i.e 98 will go to right tree as 98 is greater than 48. And so on we progress