Binary-search-tree

Question 1
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
1. 3, 5, 7, 8, 15, 19, 25
2. 5, 8, 9, 12, 10, 15, 25
3. 2, 7, 10, 8, 14, 16, 20
4. 4, 6, 7, 9, 18, 20, 25
A
1 and 4 only
B
2 and 3 only
C
2 and 4 only
D
2 only
Data-StructuresBinary-search-treeGATE 2015 [Set-1]Video-Explanation
Question 2

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

A
65
B
67
C
69
D
83
Data-StructuresBinary-Search-TreeGATE 2015 [Set-3]Video-Explanation
Question 2 Explanation: 
Question 3

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

A
O(1)
B
O(log n)
C
O(n)
D
O(n log n)
Data-StructuresBinary-search-treeGATE 2013Video-Explanation
Question 3 Explanation: 
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n).
Question 4

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

A
Θ (n log n)
B
Θ (n2n)
C
Θ (n)
D
Θ (log n)
Data-StructuresBinary-Search-TreeGATE 2012
Question 4 Explanation: 
→ Worst case running time to search for an element in a balanced binary search tree of ‘n’ elements is (log n).
→ No of elements = n.2n then search time = (log n.2n)
= (log n + log 2n)
= (log n + n log 2)
= O(n)
Question 5

Suppose we have a balanced binary search tree T holding n numbers.  We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nalogbn + mclogdn), the value of a + 10b + 100c + 1000d is ____.

A
110
B
111
C
112
D
113
AlgorithmsBinary-Search-TreeGATE 2014 [Set-3]Video-Explanation
Question 5 Explanation: 
It takes (log n) time to determine numbers n1 and n2 in balanced binary search tree T such that
1. n1 is the smallest number greater than or equal to L and there is no predecessor n1' of >n1 such that n1' is equal to n1.
2. n22' of n2 such that is equal to n2.
Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.
So time complexity is O(log n+m)
So the given expression becomes O(n0log'n+m'log0n)
And a+10b+100c+1000d = 0+10*1+100*1+1000*1 = 10+100 = 110
Because a=0, b=1, c=1 and d=0
Question 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?

A
θ(log n)
B
θ(n)
C
θ(nlog n)
D
None of the above, as the tree cannot be uniquely determined
Data-StructuresBinary-Search-TreeGATE 2008
Question 6 Explanation: 
Last element in post order is the root of tree- find this element in inorder-log n time. Now as in quick sort consider this as pivot and split the post order array into 2. All elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have k elements smaller than pivot, these elements will be same in both in-order as well as post order. Now, we already got the root, now left child is the left split and right child is the right split.
T(n) = T(k) + T(n-k-1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the in-order traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element- if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(n-k-1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 7

Postorder traversal of a given binary search tree T produces the following sequence of keys 

   10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?

A
9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
B
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
C
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
D
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Data-StructuresBinary-Search-TreeGATE 2005
Question 7 Explanation: 
Inorder traversal of any binary search tree is the sorted sequence of element in ascending order.
Question 8

How many distinct binary search trees can be created out of 4 distinct keys?

A
5
B
14
C
24
D
42
Data-StructuresBinary-Search-TreeGATE 2005
Question 8 Explanation: 
There are 2nCn / (n+1) unlabeled trees are possible.
(or)

t(0)=1
t(1)=1
t(4) = t(0)t(3) + t(1)t(2) + t(2)t(1) + t(3)t(0)
= 5+2+2+5
= 14
(or)
8C4 / 5 = 14
Question 9

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

A
2
B
3
C
4
D
6
Data-StructuresBinary-Search-TreeGATE 2004
Question 9 Explanation: 

Height of the binary search tree = 3
Question 10

Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is

A
n – k + 1
B
n – k
C
n – k – 1
D
n – k – 2
Data-StructuresBinary-Search-TreeGATE 2003
Question 10 Explanation: 
A binary search tree consists of n distinct elements. Let consider on left subtree, it consists of (k-1) elements. Then right subtree consists of (n-k) elements. From this we c an write recursive function as T(k-1)*(n-k) i.e.,
Question 11

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

A
7 5 1 0 3 2 4 6 8 9
B
0 2 4 3 1 6 5 9 8 7
C
0 1 2 3 4 5 6 7 8 9
D
9 8 6 4 2 3 0 1 5 7
Data-StructuresBinary-Search-TreeGATE 2003
Question 11 Explanation: 

Inorder: 0 1 2 3 4 5 6 7 8 9
There are 11 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access