Test by Bikram | Mock GATE | Test 2 | Question: 37

Question

Which of these statements is not true about an $AVL$ tree $T$ containing $n$ nodes?

• A. Rotations may be required during key insertion to keep $T$ balanced.
• B. The height of $T$ cannot exceed $1.5$ * $\log 2^{n}$ . And  It is possible to insert nodes into $T$ in $O$$\left ( \lg n \right )$ asymptotic algorithmic complexity.
• C. The number of interior nodes in $T$ cannot exceed the number of leaves in $T$.
• D. If each node in $T$ is augmented with an integer showing the size of that node’s sub-tree, then $T$ can be used to perform order statistic searches in $O$$\left ( \lg n \right )$ asymptotic algorithmic complexity.

Answer 1

C   The number of interior nodes in T can exceed the number of leaves in T .

 

Comments

i could not understand

interior nodes always less than leaves so is in statement thenwhy this is false?

---

Leaf nodes = Internal nodes*(n-1) +1

is valid for complete n-ary tree only, where each node has either 0 or n children

---

here, root node is also considered as an internal node .