Binary Tree Practice Questions

In a complete binary tree with $N=2$ nodes (root 1, left child 2), the traversal results are: Preorder $\{1, 2\}$, Inorder $\{2, 1\}$, and Postorder $\{2, 1\}$. Here, $LASTIN = LASTPOST = 1$ is true, but $LASTIN = LASTPRE$ is false because $1 \neq 2$. For $N=3$ nodes (root 1, left child 2, right child 3), the results are: Preorder $\{1, 2, 3\}$, Inorder $\{2, 1, 3\}$, and Postorder $\{2, 3, 1\}$. Here, $LASTIN = LASTPRE = 3$ is true, but $LASTIN = LASTPOST$ is false because $3 \neq 1$. Since no relation consistently holds for all complete binary tree structures, none of the provided options are always true.

The defined notation $(X \ Y \ Z)$ requires exactly three components: a root $X$, a left subtree $Y$, and a right subtree $Z$.
Option A is invalid because the sub-expression $(4 \ 5 \ 6 \ 7)$ contains four elements, violating the binary structure requirement.
Option B is syntactically invalid due to mismatched parentheses and an incorrect number of elements.
Option D is invalid because the subtree $(4 \ 5)$ contains only two elements, failing to provide the three required components.
Option C is valid because $1$ acts as the root, $(2 \ 3 \ 4)$ serves as the left subtree, and $(5 \ 6 \ 7)$ serves as the right subtree, perfectly adhering to the $(X \ Y \ Z)$ pattern.

The post-order traversal follows the rule: Left Subtree $\to$ Right Subtree $\to$ Root.

1. Start at node $a$. First, traverse its left subtree rooted at $b$:
2. Within subtree $b$, traverse left subtree $c$ (visits $g$, then $c$), then right node $d$, finally root $b$. Sequence so far: $g, c, d, b$.
3. Next, traverse the right subtree of $a$ (rooted at $e$):
4. Within subtree $e$, traverse left node $f$, then root $e$. Sequence so far: $g, c, d, b, f, e$.
5. Finally, visit the root $a$. The complete sequence is $g, c, d, b, f, e, a$.

Let $n_0$ be the number of nodes with 0 children (leaf nodes), $n_1$ be the number of nodes with 1 child, and $n_2$ be the number of nodes with 2 children.
The total number of nodes $N = n_0 + n_1 + n_2$.
The total number of edges $E$ in a tree is $N - 1 = n_0 + n_1 + n_2 - 1$.
Also, the total number of edges is equal to the sum of children for all nodes: $E = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2$.
Equating the two expressions for $E$: $n_0 + n_1 + n_2 - 1 = n_1 + 2n_2$.
Simplifying the equation gives $n_0 - 1 = n_2$.
Given $n$ leaf nodes ($n_0 = n$), the number of nodes of degree 2 is $n_2 = n - 1$.

Optimal binary search tree construction is a standard application of dynamic programming with a time complexity of $O(n^3)$, making statement A true. Breadth-first search (BFS) systematically traverses graph nodes and is an standard, efficient algorithm used to identify connected components by initiating traversals from unvisited vertices; therefore, the claim in statement B is false. Regarding statement C, preorder and postorder traversals are insufficient to uniquely reconstruct an arbitrary binary tree, as ambiguity arises for nodes with a single child, making this statement true. Depth-first search (DFS) is also a fundamental graph traversal algorithm known to effectively identify connected components, making statement D true. Consequently, statement B is the only false assertion among the options.

The number of rooted binary trees with $n$ nodes is given by the $n$-th Catalan number, denoted as $C_n = \frac{1}{n+1} \binom{2n}{n}$. This combinatorial sequence also counts the number of ways to fully parenthesize a product of $n+1$ matrices (matrix chain multiplication problem). Because the structure of parenthesizing $(n+1)$ matrices follows the same recurrence relation as the construction of rooted binary trees with $n$ nodes, both are represented by $C_n$. Therefore, the number of ways is correctly described by $\frac{1}{n+1} \binom{2n}{n}$ and the matrix multiplication equivalence.

[CORRECT_OPTION: A, C]

The external path length $E = \sum_{i=1}^n l_i$ of a binary tree with $n$ external nodes is minimized when the tree is as balanced as possible.
According to Kraft's inequality, the depths $l_i$ of these leaves must satisfy the constraint $\sum_{i=1}^n 2^{-l_i} = 1$.
To minimize $\sum_{i=1}^n l_i$ subject to this constraint, we apply Jensen's inequality or observe that for the function $f(x) = \log_2 x$, the minimum occurs when all $l_i$ are equal.
Setting $2^{-l_i} = \frac{1}{n}$ yields $l_i = \log_2 n$ for all $i$, representing a perfectly balanced tree.
Thus, the sum of path lengths is bounded below by $E = \sum_{i=1}^n \log_2 n = n \log_2 n$.
Therefore, $E \geq n \log_2 n$ holds for any binary tree with $n$ external nodes.

Statement A is false because overlaying manages physical memory constraints, not the CPU's fundamental address space limit. Statement C is false as depth-first search is a standard algorithm used to identify connected components in a graph. Statement D is false because, unlike (preorder + inorder) or (postorder + inorder), prefix (preorder) and postfix (postorder) traversals are insufficient to uniquely reconstruct a general binary tree. Statement B is true, as optimal binary search tree construction is efficiently solved using dynamic programming in $O(n^3)$ time. Thus, statements A, C, and D are false.

[CORRECT_OPTION: A, C, D]