0
28kviews
What is binary search tree? Explain with an example
1 Answer
1
3.1kviews
  • 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

enter image description here

Please log in to add an answer.