0
27kviews
What is binary search tree? Explain with an example
1
3.0kviews
• 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:

$$48,2,98,12,56,32,4,6$$

• 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 