## Binary-Search-Tree

 Question 1
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-Structures       Binary-Search-Tree       GATE 2015(Set-03)
Question 1 Explanation:
 Question 2
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
Algorithms       Binary-Search-Tree       Gate 2014 Set -03
Question 2 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 3
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-Structures       Binary-Search-Tree       Gate 2012
Question 3 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 4
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-Structures       Binary-Search-Tree       Gate-2008
Question 4 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 5
How many distinct binary search trees can be created out of 4 distinct keys?
 A 5 B 14 C 24 D 42
Data-Structures       Binary-Search-Tree       Gate-2005
Question 5 Explanation:
There are 2nCn / (n+1) unlabelled 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 6
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-Structures       Binary-Search-Tree       Gate-2005
Question 6 Explanation:
Inorder traversal of any binary search tree is the sorted sequence of element in ascending order.
 Question 7
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-Structures       Binary-Search-Tree       Gate-2004
Question 7 Explanation:

Height of the binary search tree = 3
 Question 8
Let T(n) be the number of different binary search trees on n distinct elements. Then
 A n – k + 1 B n – k C n – k – 1 D n – k – 2
Data-Structures       Binary-Search-Tree       Gate-2003
Question 8 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 9
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-Structures       Binary-Search-Tree       Gate-2003
Question 9 Explanation:

Inorder: 0 1 2 3 4 5 6 7 8 9
 Question 10

 A Theory Explanation is given below.
Data-Structures       Binary-Search-Tree       Gate-2001
There are 10 questions to complete.