GATE CSE 2008 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

II and III only

I and III only

III and IV only

III only

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

I, II and IV are inorder sequences of three different BSTs

I is a preorder sequence of some BST with 439 as the root

II is an inorder sequence of some BST where 121 is the root and 52 is a leaf

IV is a postorder sequence of some BST with 149 as the root

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

How many distinct BSTs can be constructed with 3 distinct keys?

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

O(Logn)

O(n)

O(nLogn)

none of the above, as the tree cannot be uniquely determined.

PREVIOUS NEXT

GATE CSE Papers

2023