Binary Search Tree Mock Test -1

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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

Click Here to Practice ALL Previous MOCK TEST FREE

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 2 Explanation:

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

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:

The traversal visits and lists each element once, so it is O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

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

Click Here to Practice ALL Previous MOCK TEST FREE

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