GATE CSE 2006 | Question: 13

Question

A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$. the root is stored at $X[1]$. For a node stored at $X[i]$, the left child, if any, is stored in $X[2i]$ and the right child, if any, in $X[2i+1]$. To be able to store any binary tree on n vertices the minimum size of $X$ should be

• A. $\log_2 n$
• B. $n$
• C. $2n+1$
• D. $2^n-1$

Comments

You just need to use common sense to solve it . Options can be eliminated easily .
Whenever you are storing an element space for its child will be reserver at locations $[2i+1]$ . This means that {$\approx 2^i $ }locations extended}
Therefore at leaf also extra $2^n -1$ space will be reserved.

---

A,B,C are just too less if we see space wise. so they can be eliminated .
 

---

   

 this is worst case : where left  null  then a  at index 1

2 index null 

b at index 3  

Here n  = 2 if we put n = 2 

then 2^n-1  will satisfied .  

---

@manas_pant Nice Observation. Worst Case Happnes when We keep increaing levels by adding nodes, then we can see the Leaf Node would be reserving indexes at 2^i.

For Example:- Root Level takes 1st index. it's left child goes to 2^1=1. Further Adding child to this children node take index 2^2=4. 

So, increasing levels in tree adds nodes in array indexes at rate of 2^i. 

Answer 1

Answer is D.

To be able to store " any " binary tree on n vertices the minimum size of X should be

" Any Binary Tree and Size should be minimum " .
So We must consider worst case binary tree for this situation and find the minimum space required .

Minimum size for $\underline{\text{any}}$ binary tree

$\implies$Minimum size of worst case binary tree

$\qquad {X[i] = node \\ X[2i] = \text{Left child} \\ X[2i+1] = Right child}$

Let $n = 3$

$X[1] = A $ $X[2] = B $ $X[3] = C$	$X[1] = A$ $ X[2] = B$ $ X[4] = C$	$X[1] = A$ $  X[3] = B$ $  X[7] = C$
$n$	$2^{n - 1}$	$2^n-1$
Minimum size Best Case binary tree		Minimum size Worst Case binary tree

Comments

If in place of minimum, the question asked for maximum size then the answer would have been same?

---

nice explanation

---

nice explain

Answer 2

Answer should be (D).

Since binary tree can be of any form, the worst case happens for right skewed binary tree. Now, root goes to index $1$, its child goes to index $3$, its child goes to index $7$ and so on the nth vertex goes to $2^n - 1$ th index of array.  

Comments

@ABKUNDAN Since its the Array representation of Binary Tree which has the very drawback that unnecessary array space is wasted if the tree is any normal Binary tree (i.e worst case 2ⁿ-1) and not a  Complete Binary tree (where in CBT its actually n).

So in such cases (any normal Binary tree), we instead prefer Linked List Representation of Binary Tree which occupies less space comparatively.

Though random access is not possible with Linked List as traversing is done via pointers and Arrays permits the use of formulae  to fetch any node randomly, so Array leads the choice when we have complete Binary tree.

---

What if asked Maximum size how do we are going to do that

---

What if asked Maximum size how do we are going to do that we can get same right

Answer 3

For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.

A
 \
   \
    B
      \
        \
         C
           \
             \
              D

Answer 4

what would be the max size of X?

 will it be  ((2^n) - 1 )  ??

Answer 5

Answer should be 2*n+1 as what if tree is right skewed