Chapter 6: Trees

Question 1

Which of the following is true about binary trees:

1. Every binary tree is either complete or full
2. Every complete binary tree is also a full binary tree
3. Every full binary tree is also a complete binary tree
4. No binary tree is both complete and full
5. None of the above

Solution

Option A is incorrect since it is not compulsory that a binary tree should be complete or full.

Option B is incorrect since a complete binary tree can have some nodes that are not filled in the last level, so a complete binary tree will not always be a full binary tree.

Option C is incorrect, as it is not always true, the following figure is a full binary tree, but not a complete binary tree:

Figure A.3: A binary tree that is full, but not complete

Option D is incorrect, as it is not always true. The following tree is both a complete and full binary tree:

Figure A.4: A binary tree, that is full and complete...