UGC NET CSE | December 2012 | Part 2 | Question: 16

Question

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

• A. Binary Search Tree
• B. AVL Tree
• C. Threaded Binary Tree
• D. Complete Binary Tree

Comments

Both B and D are correct.

If single correct comes B is safer to go with.

Answer 1

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.

Comments

Why not D?

Answer 2

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

Comments

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.