What is binary search tree? Explain with an example

3.1kviews

written 7.8 years ago by

teamques10 ★ 64k

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

ADD COMMENT EDIT