# Binary Search Tree Mock Test -1

 Question 1
The postorder traversal of a binary search tree with integer values produces the following sequence: 7, 12, 25, 47, 89, 55, 42, 17. What is the value of the left child of the root of the tree?
 A 42 B 25 C 12 D 7
Data Structure
Question 1 Explanation:
The inorder traversal of a search tree is always the sorted sequence. In this case: 7, 12, 17, 25, 42, 47, 55, 89. From the postorder traversal, we know that 17 is the root of the tree, so the segment 7, 12 corresponds to the left subtree and the segment 25, 42, 47, 55, 89 corresponds to the right subtree. The postorder traversal of the left subtree ends with 12, so this is the left child of the root node.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
A Binary Search Tree (BST) is made by including each integer in [1,100] exactly once. The depth of a node in the BST is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is_____.
 A 9 B 91 C 99 D 90
Data Structure

 Question 3
Consider the following function to traverse a search tree $t$ with integer values, where $even(m)$ returns True if $m$ is an even number and False otherwise.

function strangeOrder(t) {
if (t != NIL) {
if (even(t.value)){
strangeOrder(t.left);
strangeOrder(t.right);
print(t.value);
}
else{
print(t.value);
strangeOrder(t.right);
strangeOrder(t.left);
}
}
}

What is the complexity of this traversal for a binary search tree with n nodes?
 A O(log n) B O(n) C O(1) D O(n log n)
Data Structure
Question 3 Explanation:
 Question 4
Consider a BST containing $N$ nodes, time complexity of printing out the values stored in all of the leaf nodes in ascending order is
 A $\Theta (N \log N)$ B $\Theta (N^2)$ C $\Theta (N)$ D $\Theta (\log N)$
Data Structure
Question 4 Explanation:
Do an inorder traversal , at each node, if both of its children are NULL, print it out. Checking for NULL is constant timeoperation. Must visit each node once. So $\Theta (N)$ for traversal. Hence, ans is $\Theta (N)$.
Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 5
Two binary search tree $t_1$ and $t_2$ are equivalent if they contain exactly the same elements. That is, for all $x \in t_1,x \in t_2$, and for all $y \in t_1, y \in t_1$. What is the time complexity of an efficient algorithm to determine if BSTs $t_1$ and $t_2$ are equivalent.
Assume $|t_1|=|t_2|=n$.
 A $\Theta (n \log n)$ B $\Theta (n^2)$ C $\Theta (n)$ D $\Theta (\log n)$
Data Structure
Question 5 Explanation:
One solution is to read the elements of each tree into a sorted list using an in-order walk, and compare the resulting lists for equality. This algorithm runs in $\Theta (n)$.
Another $\Theta (n)$ solution is to put all of the elements of each tree into a hash table, and compare the resulting tables.
Click to Join Our Telegram Group for Latest Update of MOCK TEST