ISRO2009-31

Question

A full binary tree with $n$ leaves contains

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

Answer 1

A Full binary tree with $n$ leaves contains $2n-1$ nodes.

Answer 2

A full binary tree with n leaves contains 2n-1 nodes.

option (c) is correct..nn leaves contains

Answer 3

An almost complete strictly binary tree with N leaves has 2N – 1 nodes . An almost complete binary tree with N leaves that is not strictly binary has 2N nodes. 

Answer 4

Option (C)

let T be the total nodes

$T=n+i       $                      n=leaves,i=internal nodes;

so

$i = T-n$

Degree=degree of leavers + degree of internal nodes

$D=1*n+3*(i-1)+2$               

i-1 because all other internal nodes except root has degree 3 ,root has  degree 2

$D=2e$   e= edges

also $e=T-1$

so

$2(T-1)  =  n+3i-3+2$

$2T-2 = n+3i-1$

putiing value odf i $i=T-n$

$2T-2 = n+3(T-n)-1$

$2T-2 = n+3T-3n-1$

$2T = 3T-2n-1+2$

$2T = 3T-2n-1+2$

$2T = 3T-2n+1$

$T = 2n -1$

Option (C)