Question

How many empty trees hang on an ordered binary tree of n nodes?

a) n
b) n - 1
c) 2^n
d) 2^(n-1)

Answer 1

Answer: the answer your looking for is d) 2^(n-1)

Answer 2

In an ordered binary tree with n nodes, the number of empty trees (leaf or external nodes) is n+1, which is not listed among the options. The closest correct choice is 'b) n - 1', accounting for the fact that the root node is not an external node.

Step-by-step explanation:

The question "How many empty trees hang on an ordered binary tree of n nodes?" relates to the concept of an ordered binary tree in the field of computer science. In this context, "empty trees" refer to the leaf nodes or external nodes, which don't have any children.

An ordered binary tree with n nodes has exactly n+1 external nodes or 'empty trees'. This can be derived from the property that in a full binary tree with n internal nodes, there will be n+1 external nodes. However, this option is not listed in the options given. Since every internal node has exactly one more empty node, the correct option from the provided choices would be b) n - 1. This accounts for the fact that the root node is not counted as an external node since it is an internal node, and we are not including it in our count of empty trees.