The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 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 (52.1k points)
edited by | 2.8k views

6 Answers

+19 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 Veteran (62.2k points)
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.

+8 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 (2.6k points)
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 (5.1k points)
reshown by
+4 votes

both b and c are false

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

by Junior (771 points)
Here by complete binary tree, they mean all the levels must be completely filled, so C is true
+2 votes
ans b)
by Loyal (5.2k points)
–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 (7.1k points)

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
49,841 questions
54,799 answers
80,655 users