topic – RBR

Binary-Search-Tree

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

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(n^alog^bn + m^clog^dn), 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 n₁ and n₂ in balanced binary search tree T such that
1. n₁ is the smallest number greater than or equal to L and there is no predecessor n₁' of >n₁ such that n₁' is equal to n₁.
2. n₂2' of n₂ such that is equal to n₂.
Since there are m elements between n₁ and n₂, it takes ‘m’ time to add all elements between n₁ and n₂.
So time complexity is O(log n+m)
So the given expression becomes O(n⁰log'n+m'log⁰n)
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 n2ⁿ elements is

A	Θ (n log n)
B	Θ (n2ⁿ)
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.2ⁿ then search time = (log n.2ⁿ)
= (log n + log 2ⁿ)
= (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 ²ⁿC_n / (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)
⁸C₄ / 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.