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

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$
asked in DS by Veteran (59.7k points)
edited by | 2.2k views

6 Answers

+18 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.

answered by Veteran (61.2k points)
edited by
+2
Splendid !!!
+6
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.
+1
By complete binary tree they mean every node can have either two children or none, it cannot have one child.
0
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
0
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.
0
but here what you define it is almost complete binary tree..
+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=n+1

                  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 )
answered by Active (2.6k points)
0
For c) ...why root is considered as internal root?
+2
@srestha c should be false .. since it is not full binary tree..so there is not such condition that each node having 0 or 2 children..
0
@srestha it should be both b and c , right ?
c should be false
0
Then multiple choice ans was possible
0
@srestha actually not for this. That was for GATE 1999 only.
0
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
+2
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
answered by Loyal (6.1k points)
reshown by
+4 votes

both b and c are false

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

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

answered by Loyal (7.6k 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

44,150 questions
49,639 answers
163,320 comments
65,808 users