edited by
16,686 views
37 votes
37 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$
edited by

5 Answers

Best answer
36 votes
36 votes
  • 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.

edited by
13 votes
13 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 )
5 votes
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
reshown by
5 votes
5 votes

both b and c are false

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

Answer:

Related questions

29 votes
29 votes
11 answers
1
Kathleen asked Sep 25, 2014
14,544 views
A complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is g...
21 votes
21 votes
1 answer
2
Kathleen asked Sep 26, 2014
4,131 views
Derive a recurrence relation for the size of the smallest AVL tree with height $h$.What is the size of the smallest AVL tree with height $8$?
26 votes
26 votes
5 answers
3
28 votes
28 votes
5 answers
4
Kathleen asked Sep 12, 2014
8,841 views
A $2-3$ tree is such thatAll internal nodes have either $2$ or $3$ childrenAll paths from root to the leaves have the same lengthThe number of internal nodes of a $2-3$ t...