in DS
485 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.
in DS
by
485 views

4 Comments

i hink in 4th option it should be leaf node instead of node in last sentence.

0
0
yes, in option D, "maximum" was missing.
0
0
@richa B) is possible for some skewed tree
0
0

4 Answers

5 votes
5 votes
Best answer

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 Comments

Yes. so i got confused betwen FULL and COMPLETE
1
1
@richa but that is almost complete binary tree right????
0
0

 

refer to this question for detailed explanation 

B is also FALSE

http://gateoverflow.in/1661/gate1998-1-24

 

0
0
The question in the link says "pre-order and post-order" that is why it is false, the question here says "in-order and pre-order" that is why it is true, please read the questions carefully
0
0
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.

2 Comments

complete binary tree mean last level need not to be filled  and nodes are as left as possible.

by considering this  we can have structures which have internal nodes n  but leaves not n+1
0
0
B is false

Its Binary tree not BST
0
0
0 votes
0 votes

All options are correct.

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.

1 comment

If it was almost complete binary tree,then we can say that option c might get false,but for rest it's true.
0
0
Answer:

Related questions