GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
380 views

In which tree, for every node the height of its left subtree and right subtree differ almost by 1?

  1. Binary Search Tree
  2. AVL Tree
  3. Threaded Binary Tree
  4. Complete Binary Tree
asked in DS by Veteran (77.7k points)   | 380 views

2 Answers

+6 votes

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right sub-trees cannot be more than one for all nodes.

 

Hence,Option(B) AVL Tree is the correct choice.

 

answered by Veteran (31.3k points)  
+1 vote
Although by definition of AVL tree(or height balance tree) right ans is B .But i think same property also holds for complete binary tree

as from a full binary tree if we start removing elements from  the right most child we will always get a tree which is height balanced

any expert comments if i am wrong
answered by Veteran (43.9k points)  

Although  the fact you given here for complete binary tree is likely to AVL tree, but the purpose of self balancing binary search tree is different than complete binary tree.

In complete binary no  such properties(i.e. every node the height of its left subtree and right subtree differ almost by 1) holds.

Also self balancing binary search tree is used for other data structure such as priority queue.Self-balancing binary search trees can be used  to construct and maintain ordered lists

These are available Self balancing binary search tree..

Arjun sir can give more clarity here.

In a complete binary tree the property does hold :O
@Arjun Sir i mean here by definition no such rule for CBT.Because

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

But this property((i.e. every node the height of its left subtree and right subtree differ almost by 1) comes automatically in a complete binary tree.

Am i rt ?
@Arjun Sir ..In a complete binary tree why the above property does not hold  .. ?
I mean it does hold, there is not a counter example rt?
ohh sorry .. my bad .. then D should also be right option .. right sir ??
yes, though B is a safer choice.


Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1132 Points

  8. Debashish Deka

    994 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,355 questions
30,066 answers
67,371 comments
28,382 users