The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
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.5k points)
edited by | 2k views

6 Answers

+17 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 (60.8k 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 (6k 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 (775 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.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. 

answered by Loyal (7.3k points)


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

39,542 questions
46,682 answers
139,878 comments
57,690 users