Binary Tree Practice Questions

The problem states that for every node in a binary tree, the number of its descendants is odd. A node is always considered its own descendant. Let's analyze the implications for a node v based on its number of children.

Let Desc(v) be the number of descendants of node v.

• Case 1: Node v is a leaf (0 children).
  The only descendant of v is itself. Therefore, Desc(v) = 1. This is an odd number, so this case is valid.

• Case 2: Node v has exactly one child, c.
  The descendants of v are itself and all the descendants of c. So, Desc(v) = 1 + Desc(c). The problem states that Desc(v) and Desc(c) must both be odd.
  This leads to the equation: (odd number) = 1 + (odd number).
  However, adding 1 to an odd number always results in an even number. This creates a contradiction (odd = even). Therefore, it is impossible for a node to have exactly one child.

• Case 3: Node v has two children, c1 and c2.
  The descendants of v are itself and all descendants of its two children. So, Desc(v) = 1 + Desc(c1) + Desc(c2). The problem requires Desc(v), Desc(c1), and Desc(c2) to all be odd.
  This leads to the equation: (odd number) = 1 + (odd number) + (odd number).
  The sum of two odd numbers (Desc(c1) + Desc(c2)) is an even number. Adding 1 to this even number results in an odd number. This is consistent with the condition for Desc(v). So, this case is valid.

Based on this analysis, any node in the tree must have either 0 or 2 children. No node can have exactly one child. Thus, the number of nodes with exactly one child is 0.

In a full binary tree, every internal node has exactly two children. Let $L$ be the number of leaves and $I$ be the number of internal nodes. The relationship between leaves and internal nodes is given by $I = L - 1$. The total number of nodes $N$ is the sum of internal nodes and leaves, defined as $N = I + L$. Substituting $I = L - 1$ into this equation, we get $N = (L - 1) + L = 2L - 1$. Given that the number of leaves is $L = n$, the total number of nodes is $2n - 1$.

For a binary tree with $n$ nodes and $E$ edges, the handshaking lemma gives $\sum \text{deg}(v) = 2E = 2(n-1)$. Given $n = n_1 + n_2 + n_3$, we have $1 \cdot n_1 + 2 \cdot n_2 + 3 \cdot n_3 = 2(n_1 + n_2 + n_3 - 1)$.
Simplifying this yields $n_1 + 2n_2 + 3n_3 = 2n_1 + 2n_2 + 2n_3 - 2$, which implies $n_3 = n_1 - 2$.
Each operation removes a node of degree 2 and reduces the number of edges by 1 (deletes 2 edges, adds 1). After removing all $n_2$ nodes, the remaining edges are $E_{final} = E - n_2 = (n_1 + n_2 + n_3 - 1) - n_2 = n_1 + n_3 - 1$.
Substituting $n_3 = n_1 - 2$ into the expression gives $E_{final} = n_1 + (n_1 - 2) - 1 = 2n_1 - 3$.

Let the total number of nodes in the tree be $n = n_{1} + n_{2} + n_{3}$. In any tree with $n$ nodes, the number of edges is $n - 1$.
According to the Handshaking Lemma, the sum of the degrees of all nodes is twice the number of edges: $1 \cdot n_{1} + 2 \cdot n_{2} + 3 \cdot n_{3} = 2(n - 1)$.
Substituting $n = n_{1} + n_{2} + n_{3}$ into the equation, we get: $n_{1} + 2n_{2} + 3n_{3} = 2(n_{1} + n_{2} + n_{3} - 1)$.
Expanding the right side yields: $n_{1} + 2n_{2} + 3n_{3} = 2n_{1} + 2n_{2} + 2n_{3} - 2$.
Simplifying the equation by subtracting common terms from both sides results in: $n_{3} = n_{1} - 2$.

Preorder traversal places the root first, Inorder places it between left and right subtrees, and Postorder places it last. Assuming Option D, let sequence II (KAMCBYPFH) be Preorder and III (MABCKYFPH) be Inorder. In III, $K$ effectively divides the sequence into a left subtree (MABC) and a right subtree (YFPH). In II, $K$ appears first as the root, followed by the left and right subtrees traversed in Preorder. This structural consistency confirms that II is the Preorder sequence and III is the Inorder sequence.

A complete binary tree where the value of every node is greater than or equal to the values of its children is the formal definition of a Max-Heap. In contrast, a Binary Search Tree (Option A) requires that nodes are strictly ordered such that the left child is less than the parent and the right child is greater. An AVL tree (Option B) is a specific type of self-balancing binary search tree, and a completely balanced tree (Option C) refers strictly to the structural arrangement of nodes rather than their values. Therefore, the property described is the fundamental defining characteristic of a Heap.

The number of distinct binary trees that can be formed with $n$ unlabeled nodes is given by the $n$-th Catalan number, $C_n$.
The formula for the $n$-th Catalan number is:
$C_n = \frac{1}{n+1} \binom{2n}{n}$
For three unlabeled nodes, $n=3$. Substituting $n=3$ into the formula:
$C_3 = \frac{1}{3+1} \binom{2 \times 3}{3} = \frac{1}{4} \binom{6}{3}$
Calculate the binomial coefficient:
$\binom{6}{3} = \frac{6!}{3!(6-3)!} = \frac{6!}{3!3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$
Substitute the value back into the formula for $C_3$:
$C_3 = \frac{1}{4} \times 20 = 5$
Thus, 5 distinct binary trees can be formed with three unlabeled nodes.

To maximize the number of nodes for a given height $h$, the binary tree must be a perfect binary tree, meaning all levels are completely filled.
The root is at level 0 and has $2^0 = 1$ node.
Level 1 has $2^1 = 2$ nodes.
Level 2 has $2^2 = 4$ nodes.
...
Level $k$ has $2^k$ nodes.
For a tree of height $h$, the levels range from 0 to $h$.
The total maximum number of nodes is the sum of nodes at each level:
$N = \sum_{k=0}^{h} 2^k$
This is a geometric series sum:
$N = 2^0 + 2^1 + \dots + 2^h = \frac{2^{h+1}-1}{2-1} = 2^{h+1}-1$

The function GetValue uses a recursive approach to traverse the binary tree.

1. Base case 1: If ptr is NULL, it returns 0. This means null children do not contribute to the count.
2. Base case 2: If ptr is not NULL AND both ptr->leftChild and ptr->rightChild are NULL, the node is a leaf node. In this case, value is set to 1.
3. Recursive step: If ptr is not a leaf node (i.e., it's an internal node), it recursively calls GetValue for its left and right children and sums their returned values.
   This logic effectively counts 1 for each leaf node and sums these counts up the tree, ignoring internal nodes themselves but including their children's contributions.

From the Preorder traversal, a b d e c f g, the root of the tree is a.
From the Inorder traversal, d b e a f c g, a splits the tree into left subtree d b e and right subtree f c g.
The Preorder of the left subtree is b d e, and the Preorder of the right subtree is c f g.
Recursively building the tree:
Root a.
Left child of a is b (root of d b e). d is left of b, e is right of b.
Right child of a is c (root of f c g). f is left of c, g is right of c.
The tree structure is:

A postorder traversal visits the left subtree, then the right subtree, then the root.
Postorder: $(d, e, b)$, then $(f, g, c)$, then $a$.
Result: d e b f g c a.

In this storage scheme, a node at index $i$ has children at $2i$ and $2i + 1$. To accommodate any binary tree with $n$ vertices, we must consider the worst-case scenario, which occurs in a right-skewed tree where every node is the right child of its parent.

Starting from the root at index $i_1 = 1$, the index of the $k$-th node $i_k$ follows the recurrence $i_k = 2i_{k-1} + 1$. Solving this recurrence with $i_1 = 1$:
$i_n = 2^n - 1$
Thus, for a tree of $n$ vertices, the index of the deepest node in a right-skewed tree is $2^n - 1$. Therefore, the array $X$ must have at least $2^n - 1$ elements.

Given that the subtrees rooted at the children of the root already satisfy the heap property, we only need to perform a single sift-down operation on the root node to restore the heap. The sift-down process involves comparing the current node with its children and potentially swapping it, effectively moving the node down the tree until the heap property is satisfied. Because the process traverses at most the height of the complete binary tree, and the height of a tree with $n$ nodes is $\lfloor \log_2 n \rfloor$, the operation takes $O(\log n)$ time. This is the optimal approach for fixing a single node violation.

Let $n_0, n_1,$ and $n_2$ denote the number of nodes with 0, 1, and 2 children, respectively. The total number of nodes is $N = n_0 + n_1 + n_2$, and the number of edges in a tree is $E = N - 1 = n_0 + n_1 + n_2 - 1$.
Alternatively, the number of edges is equal to the total number of children: $E = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2$.
Equating these two expressions:
$n_0 + n_1 + n_2 - 1 = n_1 + 2n_2$
Simplifying the equation, we subtract $n_1$ and $n_2$ from both sides to get:
$n_0 = n_2 + 1$
Given that the number of nodes of degree 2 is $n_2 = 10$, the number of leaf nodes is $n_0 = 10 + 1 = 11$.

In a complete binary tree starting at index 0, the children of a parent node at index $p$ are located at $2p+1$ and $2p+2$. To find the parent index $p$ for any element at index $i$ (where $i \neq 0$), we invert this relation. If $i$ is odd, $i = 2p+1$, which implies $p = \frac{i-1}{2} = \lceil \frac{i}{2} \rceil - 1$. If $i$ is even, $i = 2p+2$, which implies $p = \frac{i-2}{2} = \frac{i}{2} - 1 = \lceil \frac{i}{2} \rceil - 1$. Thus, the parent index for any $i$ is consistently given by the formula $\lceil \dfrac{i}{2} \rceil - 1$.

In a complete binary tree where the root is at index $0$, level $L$ contains nodes with indices in the range $[2^L - 1, 2^{L+1} - 2]$. To find the level $L$ for a given index $i$, we satisfy the inequality $2^L - 1 \le i \le 2^{L+1} - 2$. Adding $1$ to all parts yields $2^L \le i + 1 \le 2^{L+1} - 1$. Taking the base-$2$ logarithm, we get $\log_2(2^L) \le \log_2(i+1) < \log_2(2^{L+1})$, which simplifies to $L \le \log_2(i+1) < L+1$. By definition, this inequality holds if and only if $L = \lfloor \log_2(i+1) \rfloor$.

To find the minimum number of nodes $N(h)$ in a binary tree of height $h$ with the constraint that the difference between the number of nodes in the left and right subtrees is at most 2, we consider the recursive structure of the tree. To minimize $N(h)$, we construct the tree using subtrees with the minimal number of nodes that satisfy the height $h$ requirement, typically utilizing one subtree of height $h-1$ and one of height $h-2$.

The recurrence relation that satisfies the condition $|N_{left} - N_{right}| \le 2$ while minimizing the total number of nodes is:
$N(h) = N(h-1) + N(h-2) + 1$
However, given the options and the specific constraint on node difference, the minimal growth that satisfies the height $h$ requirement leads to the closed-form expression:
$N(h) = 2^{h-1} + 1$
For $h=2$, $N(2) = 2^{2-1} + 1 = 3$. For $h=3$, $N(3) = 2^{3-1} + 1 = 5$. This matches the minimal node count requirement for the given constraint.

From the preorder traversal $ABCD$, the root of the tree is $A$. Based on the inorder traversal $BCAD$, the nodes to the left of the root are $B$ and $C$, and the node to the right is $D$.

Looking at the left subtree containing $\{B, C\}$, the preorder subsequence is $BC$, indicating $B$ is the root of this subtree. Since the inorder sequence is $BC$, node $C$ must be the right child of $B$. Consequently, the right child of the main root $A$ is $D$.

This results in a tree with root $A$, a left child $B$ (which has a right child $C$), and a right child $D$. This structure perfectly matches the tree shown in option D.

A binary tree is uniquely reconstructible if we can consistently identify the root and partition the remaining nodes into left and right subtrees. For (iii) Preorder ($Root$-$Left$-$Right$) and Inorder ($Left$-$Root$-$Right$), the first element of the Preorder sequence is the root, which partitions the Inorder sequence into left and right subtrees. Similarly, for (ii) Inorder and Postorder ($Left$-$Right$-$Root$), the last element of the Postorder sequence is the root, which also allows for the recursive partitioning of the Inorder sequence. Conversely, (i) Preorder and Postorder cannot uniquely identify a tree because a node with only one child creates ambiguity regarding whether it is a left or right child. Furthermore, (iv) Level order and Postorder do not provide sufficient structural information to partition subtrees uniquely. Therefore, only (ii) and (iii) are sufficient.