GATE CS 2000 Q1.14 — Trees

According to the problem definition, a binary tree is represented in the nested format as $(X \ Y \ Z)$, where:

• $X$ is the root node.
• $Y$ is the left subtree (which can be a single node, $NULL$, or another nested tree of the form $(A \ B \ C)$).
• $Z$ is the right subtree (which can be a single node, $NULL$, or another nested tree of the form $(A \ B \ C)$).

This means every nested parenthesis representing a subtree must contain exactly three components: the root, the left child/subtree, and the right child/subtree.

Let's evaluate each option:

• Option A: $(1 \ 2 \ (4 \ 5 \ 6 \ 7))$
  The right subtree $(4 \ 5 \ 6 \ 7)$ contains four elements inside the parentheses, which violates the $(X \ Y \ Z)$ format. Thus, it is invalid.
• Option B: $(1 \ (2 \ 3 \ 4) \ 5 \ 6) \ 7)$
  This expression has mismatched parentheses and contains too many components at the outer level. Thus, it is invalid.
• Option C: $(1 \ (2 \ 3 \ 4) \ (5 \ 6 \ 7))$
  This matches the format $(X \ Y \ Z)$ perfectly:
  • Root $X = 1$
  • Left subtree $Y = (2 \ 3 \ 4)$, which is a valid binary tree with root $2$, left child $3$, and right child $4$.
  • Right subtree $Z = (5 \ 6 \ 7)$, which is a valid binary tree with root $5$, left child $6$, and right child $7$.
  Hence, this is a valid binary tree.
• Option D: $(1 \ (2 \ 3 \ NULL) \ (4 \ 5))$
  The right subtree $(4 \ 5)$ contains only two elements inside the parentheses, violating the $(X \ Y \ Z)$ format. Thus, it is invalid.