This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Balanced Binary Tree”.
1. The figure shown below is a balanced binary tree. If node P is deleted, which of the following nodes will get unbalanced?
Explanation: If node P is removed, node U will become unbalanced because its balance factor will be -2.
2. Balanced binary tree with n items allows the lookup of an item in ____ worst-case time.
A) O(log n)
B) O(nlog 2)
Explanation: Searching for an item in balanced binary is fast, and the search’s worst-case time complexity is O. (log n).
3. Which of the following data structures can be efficiently implemented using height balanced binary search tree?
B) priority queue
D) both sets and priority queue
Explanation: Sets and priority queues can be efficiently implemented using a height-balanced binary search tree.
4. Two balanced binary trees are given with m and n elements respectively. They can be merged into a balanced binary search tree in ____ time.
D) O(mlog n)
Explanation: We first store both trees’ in-order traversals in two separate arrays, then merge these sorted sequences in O(m+n) time. The balanced tree is then built from this final sorted list.
5. 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
Explanation: In both the binary heap and the balanced binary search tree, insertion and deletion take O. (log n). However, searching in a balanced binary search tree takes O(log n), while searching in a binary heap takes O. (n). The construction of a balanced binary search tree takes O(nlog n) time, while the construction of a binary heap takes O(nlog n) time (n).
6. AVL trees are more balanced than Red-black trees.
Explanation: Since the AVL tree is shorter than the Red-black tree and both trees have the same number of elements, the AVL tree is more balanced.
7. Which of following figures is a balanced binary tree?
Explanation: The root of certain tree diagrams has a balance factor of +2, indicating that the tree is not balanced. It is a balanced tree if every node in the tree is balanced.
8. A binary tree is balanced if the difference between left and right subtree of every node is not more than ____
Explanation: The heights of two subtrees of each node in a balanced binary tree never vary by more than one in a balanced binary tree.
9. Which of the following tree data structures is not a balanced binary tree?
A) AVL tree
B) Red-black tree
C) Splay tree
Explanation: All of the tree data structures in the options are balanced, but the B-tree may have multiple children.
10. Figure below is a balanced binary tree. If a node inserted as child of the node R, how many nodes will become unbalanced?
Explanation: Only the node P will become unbalanced, with balance factor +2.
11. What will be the height of a balanced full binary tree with 8 leaves?
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.
12. 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
Explanation: The difference between the heights of a node’s left and right subtrees is known as the node’s balance factor in a binary tree.
According to Douglass Green’s book Form in Tonal Music, a balanced binary form consists of a binary form with a first section (the A section) ending in a new key and the second section ending with exactly the same cadence, now transposed to the original key, as in Bach’s piece below. A balanced binary tree is a binary tree arrangement in which the height difference between the left and right subtrees of each node is less than one. Each parent node has only one associated child node in a degenerate (or pathological) tree. As a result, the tree would behave similarly to a linked list data structure.