Binary Tree Array Implementation

Question

What must be the ideal size of array if the height of tree is ‘l’?
a) 2l-1
b) l-1
c) l
d) 2l

 

Comments

Can you tell, how you have defined height, root at height 0 or 1

Answer 1

Assuming root at height 1

Since maximum elements in a tree (complete binary tree) of height l will be (2^l)-1 so a good array size must be that (since a binary tree node may not always have 2 children but for safety we should take it).

Therefore, none of your answer is correct it should be (2^l) -1

Answer 2

Answer will be $2^{l}-1$ if you consider the array indexing starting from 1

At height l=1--$2^1-1$ only one node

l=2  -- $2^2-1$node

At l height max node will be $2^l-1$

So this is max size of array that would be required