Which of the following statements is false?
1998
Which of the following statements is false?
- A.
A tree with n nodes has n - 1 edges.
- B.
A labeled rooted binary tree can be uniquely constructed from its preorder and postorder traversal results.
- C.
A complete binary tree with n internal nodes has n + 1 leaves.
- D.
The maximum number of nodes in a binary tree of height h is 2^(h + 1) - 1.
Attempted by 46 students.
Show answer & explanation
Correct answer: B
Option B is false. A general labeled rooted binary tree cannot be uniquely reconstructed from only preorder and postorder traversals. For example, preorder A, B and postorder B, A can represent a tree where B is the left child of A, or a tree where B is the right child of A. Both give the same preorder and postorder sequences.
Option A is true because any tree with n nodes has n - 1 edges. Option C is true under the complete/full binary tree convention used in this question: if each internal node has two children, then leaves = internal nodes + 1. Option D is true because the maximum number of nodes in a binary tree of height h is 1 + 2 + ... + 2^h = 2^(h + 1) - 1. Hence, option B is the false statement.