1,036 views
2 votes
2 votes

Which of the following statements is false?

  1. A tree with $n$ nodes has $n-1$ edges
  2. A labeled rooted binary tree can be uniquely constructed given its in-order and pre-order 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$ where $h$ is the maximum distance of a node from root.

3 Answers

Best answer
5 votes
5 votes

complete binary tree is abinary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible..

selected by
4 votes
4 votes

I think all options are right here.

A)True-Because if a tree have more than n-1 edges it will form cycle.

B)True

D)True)---In complete binary tree with height h, no. of nodes are 2h+1–1

C)True)-->According to "Discrete Mathematics and Its Applications" by " Kenneth H. Rosen"

page no-1018

Page.no-777

http://www2.fiit.stuba.sk/~kvasnicka/Mathematics%20for%20Informatics/Rosen_Discrete_Mathematics_and_Its_Applications_7th_Edition.pdf

And in a binary tree if there are  n+1 leafs then there are n nodes with exactly 2 childs.

So in complete binary tree given above,if there are n internal nodes then all of them will have 2 childs,so total no of leafs are n+1.

Also there are slight variations in the defination of complete binary tree,so it should be provided in question.

0 votes
0 votes

Options A, B and D are undoubtedly true.

For Option C, "complete binary tree" — the definitions of types of binary tree is not well standardized.

According to Kenneth H. Rosen,

  1. Full binary tree => Each intermediate node has exactly 2 children.
     
  2. Complete binary tree =>  Each intermediate node has exactly 2 children AND all the leafs must be at the same level.
     
  3. Nearly/Almost complete binary tree => Complete binary tree upto all levels, except possibly the last, in which nodes are as left as possible. (Heap structure).

Source: https://www.cs.drexel.edu/~amd435/courses/cs260/lectures/L-3_Trees_and_Huffman_1P.pdf

In BOTH a full and a complete binary tree, if the number of intermediate nodes is $n$, then the number of leafs is $n+1$

Which makes Option B true.

 

None of the options is correct here.

Answer:

Related questions

6 votes
6 votes
5 answers
2
0 votes
0 votes
1 answer
3
Arjun asked Oct 10, 2016
284 views
Consider the array given below:20 10 9 8 7 6 5It isa full binary tree in array representationa complete binary tree in array representationa max-heap in array representat...
1 votes
1 votes
2 answers
4
Arjun asked Oct 10, 2016
766 views
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____