The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
2.6k views

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

  1. $\log_2 n$
  2. $n$
  3. $2n+1$
  4. $2^n-1$
asked in DS by Active (3.7k points)
edited by | 2.6k views

4 Answers

+32 votes
Best answer

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
answered by Boss (22.1k points)
edited by
+2
Shandaar Bro @pc
0
what is the maximum size for worst case then?
+2

here "center of the question" is the word "ANY BINARY TREE"

0
In gate exam there are limited time and too much pressure ,in those moments is it possible to think this type of great logic with accuracy?? anyway too good explanation.
0
very nice answer ...
0

I think it must be n,because when we asked to find minium it should be minimum of either best or worst case.

For ex: when we asked to find minimum number of comparisons in insertion sort  then it will be minium(0(n-1)) when we have best case input not for worst case which is 0(n2).

0
maza aa gaya @pc sir
+32 votes

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.  

answered by Loyal (6.8k points)
edited by
+3
@Arjun Since question is asking for minimum size of X, so we should go with a complete binary tree. That way only space of n will be required.
+2
minimum size for any binary tree, hence we need to consider all possibilities
0
why we can store n vertices in 2^n-1 array space why not n space

here n vertices means all vertices of the complete binary tree(included left child and right child of all nodes)
0

@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 2n-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.

+11 votes

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
answered by Boss (45.1k points)
–2 votes
what would be the max size of X?

 will it be  ((2^n) - 1 )  ??
answered by (265 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,112 questions
45,619 answers
132,314 comments
49,297 users