GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 36

Answer 1

Given , N(h-2) = m

                        N(h-3) = k ;

The formula for AVL Tree Height is given as :

                             N(h) = N(h-1) + N(h-2) + 1      // N: # Node

Now , N(h-1) = N(h-2) + N(h-3) +1  // substitute in above equation,

                          N(h) =  N(h-2) + N(h-3) + 1 + N(h-2) +1

                          N(h) = 2*N(h-2) + N(h-3) + 2

                          N(h) = 2m+k+2

Comments

@thecoderyabham, here the question is asking for smallest AVL tree of height h with given number of nodes. For smallest AVL tree, we need to stuff maximum number of nodes in each level. So shouldn’t the recurrence relation go like this:
N(h) = 1 + 2*N(h-1) ?
Correct me if I’m wrong.