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

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 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

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 \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

Click Here to Practice ALL Previous MOCK TEST FREE


There are 5 questions to complete.

Suggested Mock Test For You.

ALL FREE Mock Test of GATE CSE

GATE CSE Previous Years Questions on Binary Search Tree

GATE CSE Previous Years Questions on Data Structure

Leave a Comment