Consider the following nested representation of binary trees: (X Y Z)…
2000
Consider the following nested representation of binary trees: (X Y Z) indicates that Y and Z are the left and right subtrees, respectively, of node X. Note that Y and Z may be NULL or further nested. Which of the following represents a valid binary tree?
- A.
(1 2 (4 5 6 7))
- B.
(1 (2 3 4) 5 6) 7)
- C.
(1 (2 3 4) (5 6 7))
- D.
(1 (2 3 NULL) (4 5))
Attempted by 51 students.
Show answer & explanation
Correct answer: C
In this notation, every non-NULL tree must have exactly three components inside a pair of parentheses: the root, the left subtree, and the right subtree.
Option C is (1 (2 3 4) (5 6 7)). The root is 1, its left subtree is (2 3 4), and its right subtree is (5 6 7). Each nested subtree also has exactly three components, so it is a valid binary tree representation.
Option A is invalid because (4 5 6 7) has four components. Option B has mismatched parentheses and too many top-level components. Option D is invalid because (4 5) has only two components. Therefore, option C is correct.