Balanced Binary Tree Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Balanced Binary Tree”.

1. What will be the height of a balanced full binary tree with 8 leaves?
a) 8
b) 5
c) 6
d) 4
View Answer

Answer: d
Explanation: A balanced full binary tree with l leaves has height h, where h = log2l + 1.
So, the height of a balanced full binary tree with 8 leaves = log28 + 1 = 3 + 1 = 4.
advertisement

2. The balance factor of a node in a binary tree is defined as _____
a) addition of heights of left and right subtrees
b) height of right subtree minus height of left subtree
c) height of left subtree minus height of right subtree
d) height of right subtree minus one
View Answer

Answer: c
Explanation: For a node in a binary tree, the difference between the heights of its left subtree and right subtree is known as balance factor of the node.

3. Figure below is a balanced binary tree. If a node inserted as child of the node R, how many nodes will become unbalanced?
balanced-binary-tree-questions-answers-q3
a) 2
b) 1
c) 3
d) 0
View Answer

Answer: b
Explanation: Only the node P will become unbalanced, with balance factor +2.
advertisement
advertisement

4. A binary tree is balanced if the difference between left and right subtree of every node is not more than ____
a) 1
b) 3
c) 2
d) 0
View Answer

Answer: a
Explanation: In a balanced binary tree the heights of two subtrees of every node never differ by more than 1.

5. Which of the following tree data structures is not a balanced binary tree?
a) AVL tree
b) Red-black tree
c) Splay tree
d) B-tree
View Answer

Answer: d
Explanation: All the tree data structures given in options are balanced, but B-tree can have more than two children.
advertisement

6. Which of following figures is a balanced binary tree?
a)balanced-binary-tree-questions-answers-q6a
b) balanced-binary-tree-questions-answers-q6b
c) balanced-binary-tree-questions-answers-q6c
d)balanced-binary-tree-questions-answers-q6d
View Answer

Answer: b
Explanation: In Some tree diagrams, the root of tree has balance factor +2, so the tree is not balanced. If every node in the tree is balanced, then it’s a balanced tree.

7. Balanced binary tree with n items allows the lookup of an item in ____ worst-case time.
a) O(log n)
b) O(nlog 2)
c) O(n)
d) O(1)
View Answer

Answer: a
Explanation: Searching an item in balanced binary is fast and worst-case time complexity of the search is O(log n).
advertisement

8. Which of the following data structures can be efficiently implemented using height balanced binary search tree?
a) sets
b) priority queue
c) heap
d) both sets and priority queue
View Answer

Answer: d
Explanation: Height-Balanced binary search tree can provide an efficient implementation of sets, priority queues.

9. Two balanced binary trees are given with m and n elements respectively. They can be merged into a balanced binary search tree in ____ time.
a) O(m+n)
b) O(mn)
c) O(m)
d) O(mlog n)
View Answer

Answer: a
Explanation: First we store the in-order traversals of both the trees in two separate arrays and then we can merge these sorted sequences in O(m+n) time. And then we construct the balanced tree from this final sorted array.
advertisement

10. Which of the following is an advantage of balanced binary search tree, like AVL tree, compared to binary heap?
a) insertion takes less time
b) deletion takes less time
c) searching takes less time
d) construction of the tree takes less time than binary heap
View Answer

Answer: a
Explanation: Insertion and deletion, in both the binary heap and balanced binary search tree takes O(log n). But searching in balanced binary search tree requires O(log n) while binary heap takes O(n). Construction of balanced binary search tree takes O(nlog n) time while binary heap takes O(n).

11. AVL trees are more balanced than Red-black trees.
a) True
b) False
View Answer

Answer: a
Explanation: AVL tree is more balanced than a Red-black tree because AVL tree has less height than Red-black tree given that both trees have the same number of elements.

12. The figure shown below is a balanced binary tree. If node P is deleted, which of the following nodes will get unbalanced?
balanced-binary-tree-questions-answers-q12
a) U
b) M
c) H
d) A
View Answer

Answer: a
Explanation: Node U will get unbalanced if node P is deleted, because it’s balance factor will become -2.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter