GATE CS 1987 Q2g — Trees

The given statement is FALSE (represented as 0).

A binary tree is defined as a tree structure where each node has at most two children. There is no restriction on the number of leaf nodes being a power of $2$.

Counterexample:

Consider the following binary tree:

      A
     / \
    B   C
   / \
  D   E

In this tree:

• The leaf nodes are $C$, $D$, and $E$.
• The total number of leaves is $3$, which is not a power of $2$ ($2^k$).
• Every node has at most $2$ children, making it a valid binary tree.

Since we have a valid binary tree with $3$ leaves, the statement "If the number of leaves in a tree is not a power of $2$, then the tree is not a binary tree" is false.