The Gateway to Computer Science Excellence
+23 votes

Which of the following statements is false?

  1.  A tree with a $n$ nodes has $(n – 1)$ edges
  2.  A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
  3.  A complete binary tree with $n$ internal nodes has $(n + 1)$ leaves.
  4.  The maximum number of nodes in a binary tree of height h is $2^{h+1} - 1$
in DS by Veteran
edited by | 3.8k views

1. Strict binary tree :

$\rightarrow$ Every node of tree must have either 0 or 2 child  

2. Complete binary tree :

$\rightarrow$ CBT of $l$ levels must have $l-1$ levels fully occupied

$\rightarrow l^{th}$ level nodes can be added left to right

$\rightarrow$ CBT of height h has $2^h$ to $2^{h+1}-1$ nodes

3. Full binary tree :

$\rightarrow$ Every node must have 0 or 2 child and all the leaf nodes must be at the same level.

$\rightarrow$ CBT of height h has $2^{h+1}-1$ nodes

 $*$ Every FBT is CBT

$In\ question\ sometimes:$

$CBT\rightarrow ACBT$

$FBT\rightarrow CBT$

6 Answers

+21 votes
Best answer
  • Tree with $n$ nodes must have $n-1$ edges.
  • A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results. (inorder must be needed with either preorder or postorder for that)
  • A complete binary tree with $n$ nodes can have $n$ leaves also 
  • Example:

Since: A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. So false

  •  The maximum number of nodes in a binary tree of height $h$ is 

              $1+2+4+.....+2^h=2^{h+1}-1$ So true

Answer is b and c both.

Since, $2$ answers are there I would choose b, because in some places by "complete" binary tree they mean "full binary tree" which has all the levels completely filled.

by Boss
edited by
Splendid !!!
This is "almost complete"   so only B should be the answer.
No worries, in gate definitely they will mention the definition of "complete" every time.
By complete binary tree they mean every node can have either two children or none, it cannot have one child.
if you analyze other gate questions then complete binary tree should have either 2 or zero child so if they are not defining it , we should assume this definition  only, i think.

so only option b is false
B and C both are false.

Only BST can be constructed with either pre-order or post-order.

C is false because, take an example with n = 2. It's a complete binary tree but has 1 internal and 1 leaf node, which contradicts the statement.
but here what you define it is almost complete binary tree..

A complete binary tree with n internal nodes has n+1 leaves.

This statement is not false. 

Because it clearly mentions 'complete binary tree'  not Nearly complete binary tree.

Cormen differentiates it well. 

So, only B is false and answer too.

A complete binary tree with n nodes can have n leaves also .

Can anyone give some example for this kind of tree .
Draw tree with $2$ and $1$ nodes.
+9 votes
A) True

B) From a given inorder and preorder/postorder a binary tree can be constructed. By preorder or post oredr binary tree not possible to construct. Hence False.

C) A complete binary tree of height h( say)

    Total internal nodes 1+2+4+8+....+ 2^h-1=2^h-1=n


                  2^h is nothing but total number of leaves in tree hence  C is true

D) 1+2+4+.....+2^h=2^h+1-1    ( True )
by Active
For c) ...why root is considered as internal root?
@srestha c should be false .. since it is not full binary there is not such condition that each node having 0 or 2 children..
@srestha it should be both b and c , right ?
c should be false
Then multiple choice ans was possible
@srestha actually not for this. That was for GATE 1999 only.
yes then B) should be answer.

Because only BST we can construct the tree from only postorder or preorder traversal.

For binary tree it is not possible
yes, b is the one you should pick for exam. C could be true based on definition. Also we do not know the exact question which was asked as that is not stored anywhere now.
+5 votes
option (b) and (c) are false ,

for option (c) since last level of complete tree need not be full.

counter example (1) make complete tree of 2 node ,

counter example (2) make complete tree of 4 node
by Active
reshown by
+4 votes

both b and c are false

For c - no of internal nodes  = 6 and no of leaves = 6

by Junior
Here by complete binary tree, they mean all the levels must be completely filled, so C is true
+2 votes
ans b)
by Active
–1 vote

Option C will be true in case of strictly binary tree in which each non leaf node has non empty left and right child. 

by Loyal
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
52,215 questions
60,009 answers
94,696 users