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

Dark Mode

2 votes

Which of the following statements is false?

- A tree with $n$ nodes has $n-1$ edges
- A labeled rooted binary tree can be uniquely constructed given its in-order and pre-order traversal results.
- A complete binary tree with $n$ internal nodes has $n+1$ leaves
- 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.

5 votes

Best answer

refer to this question for detailed explanation

B is also FALSE

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

0

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 2* ^{h+1}*–1

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

**page no-1018**

**Page.no-777**

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

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,

- Full binary tree => Each intermediate node has exactly 2 children.

- Complete binary tree => Each intermediate node has exactly 2 children AND all the leafs must be at the same level.

- 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

Which makes Option B true.

**None of the options is correct here.**