edited by
4,239 views
0 votes
0 votes

The minimum size that an array may require to store a binary tree with n nodes

  1. $2^{\left \lceil(log_2(n+1))  \right \rceil -1}$
  2. $2n-1$
  3. $2n-n+1$
  4. $n+1$
edited by

3 Answers

3 votes
3 votes

In the question it is clearly mentioned as "The minimum size of an array that it may require to store a binary tree with n nodes" , In this case you need to take the best case possible that is Balanced Complete Tree

The minimum size is required is 2Hieght of Tree-1

Hieght of Tree is Log2n+1 (If you take root is in hieght 0)

The minimum size is required is 2log2(n+1) -1

1 votes
1 votes

Try to consider all possible trees, like complete binary tree or right skew tree etc.

when you try with all possible trees you'll find out that array size somewhat equal to number of nodes in complete binary tree.

For right skew tree with 4 nodes, we need maximum size of an array that is 15([2^n] -1)

But, here they asked about minimum size, so they are talking about complete binary tree.

Size of array required= $2^{\left \lceil log(n+1) \right \rceil}-1$

 

Related questions

3 votes
3 votes
5 answers
2
srestha asked May 22, 2019
1,800 views
Consider the following function height, to which pointer to the root node of a binary tree shown below is passedNote that max(a,b) defined by #define max(a,b) (a>b)?a:b.i...
2 votes
2 votes
3 answers
3
0 votes
0 votes
0 answers
4