1

Be an avl tree with 20 nodes with values from 1 to 20. What are the possible values for the root node. ? I was thinking to find minimum and maximum height but I don't know what to do after that. Does anybody have an idea?

UPDATE: THe problem is to find the possibles values for root nodes. I have to respond to the following questions:

Can 1 value be the values of root node?

Can 2 value be the values of root node?

...

Can 20 value be the values of root node?

MSD561
  • 113

1 Answers1

0

The minimum and maximum number of nodes in an AVL tree of height $h$ is as follows: $$\begin{array}{l|cc|} h&0&1&2&3&4&\ldots\\ \hline \min&0&1&2&4&7&\ldots\\ \max&0&1&3&7&15&\ldots \end{array}$$

So when the left subtree has height $3$ and the right subtree has height $4$ then in the extreme unbalanced case the left and righ subtrees have $4$ and $15$ nodes respectively. Together with the root this makes $20$ nodes in total. Therefore the value at the root is at least $5$. A similar argument shows, swapping left and right, that the value at the root is at most $16$.

WimC
  • 32,192
  • 2
  • 48
  • 88
  • How it is possible for a height of 3 the minimum number of nodes to be 4. I tried to draw such a tree but it is not possible. – MSD561 Jul 10 '16 at 08:23
  • I find your mistake. You shift the rows with minimum and maximum. The Minimum and maximum for h(0) is 1. – MSD561 Jul 10 '16 at 08:44
  • I counted height in numbers of nodes on a path, not the number of edges. – WimC Jul 10 '16 at 13:26