ACtE07 · Chapter 7Data Structures, DBMS & Operating Systems🏛️ Past Licensure QuestionID: caa63322
If an AVL balanced tree has 7 nodes, starting from level zero, what is the maximum height the tree can reach?
If an AVL balanced tree has 7 nodes, starting from level zero, what is the maximum height the tree can reach?
Multiple Choice Options
- A
1
- B
2
- C✓ Correct Option
3
- D
4
Detailed Technical Solution & Explanation
In an AVL tree, the minimum number of nodes required to form a tree of height (with the root node at height 0) is defined by Fibonacci-like recurrence:
Calculating for successive heights:
•
Height 0: node
•
Height 1: nodes
•
Height 2: nodes
•
Height 3: nodes
•
Height 4: nodes
With 7 nodes, the tree satisfies . Thus, the maximum possible height is 3.
Option Analysis:
•
Option A (1): Incorrect. A height of 1 requires a minimum of 2 nodes, but 7 nodes can form a much deeper balanced tree.
•
Option B (2): Incorrect. A complete binary tree with 7 nodes has height 2, but the question asks for the maximum possible height of an AVL tree, which is reached when balance factors are .
•
Option C (3): Correct. Minimum nodes for height 3 is exactly .
•
Option D (4): Incorrect. Reaching height 4 requires at least 12 nodes ().
Reference: Demo2 · Set 2NEC Licensure Syllabus