Binary Search Tree Practice Questions

An AVL tree is a self-balancing binary search tree that maintains a height of $O(\log n)$, ensuring the worst-case search complexity is $\Theta(\log n)$. In contrast, a standard binary search tree (BST) is not guaranteed to be balanced; in the worst-case scenario (a skewed tree), the tree height becomes $O(n)$, leading to a search complexity of $O(n)$. Options B, C, and D are incorrect because they misstate these fundamental asymptotic bounds: complete binary trees do not inherently support logarithmic search without further properties, and AVL tree search complexity is independent of $\Theta(n \log n)$. Thus, only Option A accurately describes the search complexities.

In a Binary Search Tree (BST) search for key $K=273$, if we encounter node $N$, the next node must be in the range $[min, N)$ if $K < N$, or $(N, max]$ if $K > N$. We evaluate each sequence:

I. $285 \to 376$: Since $273 < 285$, we must move left; however, $376 > 285$, which is invalid.
II. $381 \to 472$: After $381$ (where $273 < 381$), we must move left; $472 > 381$, which is invalid.
III. $142(R) \to 248(R) \to 520(L) \to 386(L) \to 345(L) \to 270(R) \to 307(L)$: Each step follows the $K=273$ constraint within the narrowing range, making it a valid path.
IV. $395 \to 463$: Since $273 < 395$, we must move left; $463 > 395$, which is invalid.

An inorder traversal of a Binary Search Tree (BST) must result in a sorted sequence of keys. Sequence II ($52, 97, 121, 195, 242, 381, 472$) is sorted, so it can be an inorder traversal. If $121$ is the root, all elements smaller than $121$ ({52, 97}$) belong to the left subtree, and all larger elements (\{195, 242, 381, 472\}$) belong to the right subtree. Within the left subtree $\{52, 97\}$, $97$ must be the parent of $52$ (where $52$ is the left child of $97$), confirming that $52$ is a leaf node. Options A, B, and D fail because sequence I is not sorted (inorder), sequence I does not start with $439$ (preorder), and sequence IV's last element is $270$, not $149$ (postorder).

The number of distinct Binary Search Trees (BSTs) that can be constructed with $n$ distinct keys is given by the $n$-th Catalan number, $C_n = \frac{1}{n+1} \binom{2n}{n}$. For $n=3$, we apply the formula:
$C_3 = \frac{1}{3+1} \binom{2 \times 3}{3} = \frac{1}{4} \binom{6}{3}$
Calculating the binomial coefficient yields $\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$.
Substituting this back, we get $C_3 = \frac{20}{4} = 5$.
Thus, there are 5 distinct BSTs possible for 3 keys.

The postorder traversal $P$ of a BST is structured as $[\text{Left Subtree}, \text{Right Subtree}, \text{Root}]$. Consequently, the last element $p_n$ of the sequence is always the root of the BST. Due to the BST property, all elements in the left subtree are smaller than $p_n$, and all elements in the right subtree are larger than $p_n$. By processing the postorder array in reverse order (Root, then Right Subtree, then Left Subtree) and maintaining valid $(\text{min}, \text{max})$ value constraints for each node, we ensure each node is visited exactly once. This approach avoids redundant searches and reconstructs the tree in $\Theta(n)$ time.

The search path to the node containing $60$ consists of two sets of nodes: $L = \{10, 20, 40, 50\}$ (nodes $< 60$) and $R = \{70, 80, 90\}$ (nodes $> 60$).
In a BST, nodes in $L$ must appear in strictly increasing order, and nodes in $R$ must appear in strictly decreasing order, as each subsequent node must be a child of the previous one.
Any valid search path is an interleaving of these two ordered subsequences.
The number of distinct paths is the number of ways to choose the $3$ positions for the nodes in $R$ out of the $7$ total positions in the sequence, which is given by $\binom{7}{3}$.
$\binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$.

In a Binary Search Tree, every node in the search path for a value $T$ must define an interval $(L, R)$ that narrows based on whether the current node is greater or less than $T$. For option C:

1. $9$: Since $55 > 9$, the range becomes $(9, 100]$.
2. $85$: Since $55 < 85$, the range becomes $(9, 85)$.
3. $47$: Since $55 > 47$, the range becomes $(47, 85)$.
4. $68$: Since $55 < 68$, the range becomes $(47, 68)$.
   The next node $43$ is outside the valid range $(47, 68)$ because $43 < 47$, making this sequence impossible.

In a binary search tree (BST) constructed from the set of numbers $\{1, 2, \dots, n\}$, the first number inserted becomes the root of the tree. Let the root value be $k$. By the properties of a BST, all nodes in the left subtree are less than $k$, and all nodes in the right subtree are greater than $k$. The set of numbers greater than $k$ in the range $\{1, \dots, n\}$ is $\{k+1, k+2, \dots, n\}$. The number of elements in this set is $n - (k + 1) + 1 = n - k$. Given that the right subtree contains $p$ nodes, we set $n - k = p$, which simplifies to $k = n - p$. Thus, the first number inserted is $n - p$.

In a BST, the first element of the pre-order sequence ($5, 3, 1, 2, 4, 6, 8, 7$) is the root. Elements smaller than $5$ ($3, 1, 2, 4$) form the left subtree, and elements larger than $5$ ($6, 8, 7$) form the right subtree. Following the BST property, the left subtree ($3, 1, 2, 4$) has $3$ as the root, with $1$ as the left child, $2$ as $1$'s right child, and $4$ as $3$'s right child. The right subtree ($6, 8, 7$) has $6$ as the root, with $8$ as its right child and $7$ as $8$'s left child.

Traversing the tree in post-order ($Left, Right, Root$):

1. Left Subtree ($3, 1, 2, 4$): Traverse $1$ (no left child, right child $2 \to 2, 1$), then traverse $4$ ($4$), then root $3 \to 2, 1, 4, 3$.
2. Right Subtree ($6, 8, 7$): Traverse left child of $6$ (none), traverse right child of $6$ ($8 \to$ left child $7 \to 7, 8$), then root $6 \to 7, 8, 6$.
3. Combine: Appending the root $5$ yields $2, 1, 4, 3, 7, 8, 6, 5$.

A fundamental property of any Binary Search Tree (BST) is that its in-order traversal always produces the keys in sorted, ascending order. The post-order traversal sequence provided contains the complete set of keys present in the tree: $\{10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29\}$. To determine the in-order traversal, one simply needs to sort this set of keys. Sorting these values yields the sequence: $9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95$. This sorted result matches Option A exactly.

The number of structurally distinct binary search trees that can be formed from $n$ distinct keys is given by the $n$-th Catalan number, defined as $C_n = \frac{1}{n+1} \binom{2n}{n}$.
For $n = 4$ keys, we substitute into the formula: $C_4 = \frac{1}{4+1} \binom{8}{4}$.
Calculating the binomial coefficient, we have $\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$.
Dividing this result by $n+1 = 5$, we obtain $C_4 = \frac{70}{5} = 14$.
Therefore, there are 14 distinct binary search trees that can be created.

The binary search tree is constructed by inserting nodes sequentially: $10$ is the root, $1$ becomes the left child of $10$, $3$ is the right child of $1$, and $5$ is the right child of $3$.
Then, $15$ is placed as the right child of $10$, with $12$ as the left child of $15$ and $16$ as the right child of $15$.
The structure results in depth levels: Level 0: $\{10\}$; Level 1: $\{1, 15\}$; Level 2: $\{3, 12, 16\}$; Level 3: $\{5\}$.
The height is the maximum number of edges from the root to any leaf node.
The deepest node is $5$, located at a distance of $3$ edges from the root ($10 \to 1 \to 3 \to 5$).

An inorder traversal of any Binary Search Tree (BST) visits nodes in non-decreasing order. By definition, for every node $N$, all values in the left subtree are less than $N$ and all values in the right subtree are greater than $N$. Consequently, regardless of the specific insertion order of the numbers $\{7, 5, 1, 8, 3, 6, 0, 9, 4, 2\}$, the inorder traversal sequence will always result in the elements arranged in ascending order. Sorting the given set produces the sequence $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$.

For a set of $n$ distinct elements, choosing the $k$-th smallest element as the root leaves $k-1$ elements for the left subtree and $n-k$ elements for the right subtree.
The number of ways to construct the left subtree is $T(k-1)$ and the right subtree is $T(n-k)$.
By the rule of product, the total number of binary search trees with the $k$-th element as the root is $T(k-1) \cdot T(n-k)$.
Summing over all possible root positions $k$ from $1$ to $n$, we obtain the recurrence relation $T(n) = \sum_{k=1}^{n} T(k-1)T(n-k)$.
Comparing this with the given form $\sum_{k=1}^{n} T(k-1)T(x)$, we conclude that $x = n-k$.

For a binary search tree (BST) pre-order traversal, the first value is the root. With root $5$, all values $< 5$ (i.e., $\{1, 2, 3, 4\}$) form the left subtree, and values $> 5$ (i.e., $\{6, 7, 8\}$) form the right subtree.
In option D ($5, 3, 1, 2, 4, 7, 6, 8$), the sequence $3, 1, 2, 4$ represents the left subtree: $3$ is the root, $1$ is its left child, $2$ is the right child of $1$, and $4$ is the right child of $3$.
The sequence $7, 6, 8$ represents the right subtree: $7$ is the root, $6$ is its left child, and $8$ is its right child.
Since this structure satisfies the BST property where for any node $N$, all left descendants are $< N$ and all right descendants are $> N$, the sequence is valid.

The root of the binary search tree is $50$. Any integer smaller than $50$ belongs to the left subtree, and any integer larger than $50$ belongs to the right subtree.

1. Left subtree elements (all $< 50$): $\{15, 5, 20, 3, 8, 37, 24\}$. Counting these gives $7$ nodes.
2. Right subtree elements (all $> 50$): $\{62, 58, 91, 60\}$. Counting these gives $4$ nodes.
3. The root $50$ divides the remaining $11$ elements into a left subtree of size $7$ and a right subtree of size $4$.

Thus, the number of nodes in the left and right subtrees are $7$ and $4$ respectively.