The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged binarysearchtree
+17
votes
3
answers
1
GATE2006IT45
Suppose that we have numbers between $1$ and $100$ in a binary search tree and want to search for the number $55$. Which of the following sequences CANNOT be the sequence of nodes examined? $\{10, 75, 64, 43, 60, 57, 55\}$ $\{90, 12, 68, 34, 62, 45, 55\}$ $\{9, 85, 47, 68, 43, 57, 55\}$ $\{79, 14, 72, 56, 16, 53, 55\}$
asked
Nov 1, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

4.4k
views
gate2006it
datastructure
binarysearchtree
normal
+84
votes
7
answers
2
GATE2007IT29
When searching for the key value $60$ in a binary search tree, nodes containing the key values $10, 20, 40, 50, 70, 80, 90$ are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value $60$? $35$ $64$ $128$ $5040$
asked
Oct 30, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

11.1k
views
gate2007it
datastructure
binarysearchtree
normal
+19
votes
1
answer
3
GATE2008IT73
How many distinct BSTs can be constructed with $3$ distinct keys? $4$ $5$ $6$ $9$
asked
Oct 29, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

1.7k
views
gate2008it
datastructure
binarysearchtree
normal
+25
votes
3
answers
4
GATE2008IT72
A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys. $81, 537, 102, 439, 285, 376, 305$ $52, 97, 121, 195, 242, 381, 472$ $142, 248, 520, 386, 345, 270, 307$ ... 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
asked
Oct 29, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

1.4k
views
gate2008it
datastructure
binarysearchtree
easy
+36
votes
4
answers
5
GATE2008IT71
A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys. $81, 537, 102, 439, 285, 376, 305$ $52, 97, 121, 195, 242, 381, 472$ $142, 248, 520, 386, 345, 270, 307$ ... 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
asked
Oct 29, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

3.5k
views
gate2008it
datastructure
binarysearchtree
normal
+15
votes
2
answers
6
GATE2008IT12
Which of the following is TRUE? The cost of searching an AVL tree is $\Theta (\log n)$ but that of a binary search tree is $O(n)$ The cost of searching an AVL tree is $\Theta (\log n)$ but that of a complete binary tree is $\Theta (n \log n)$ The cost of ... tree is $\Theta(n)$ The cost of searching an AVL tree is $\Theta (n \log n)$ but that of a binary search tree is $O(n)$
asked
Oct 28, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

1.5k
views
gate2008it
datastructure
binarysearchtree
easy
+26
votes
4
answers
7
GATE19964
A binary search tree is used to locate the number $43$ ...
asked
Oct 9, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

5.3k
views
gate1996
datastructure
binarysearchtree
normal
+17
votes
3
answers
8
GATE19962.14
A binary search tree is generated by inserting in order the following integers: $50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$ The number of nodes in the left subtree and right subtree of the root respectively is $(4, 7)$ $(7, 4)$ $(8, 3)$ $(3, 8)$
asked
Oct 9, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

2.1k
views
gate1996
datastructure
binarysearchtree
normal
+59
votes
6
answers
9
GATE2014339
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^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.
asked
Sep 28, 2014
in
DS
by
jothee
Veteran
(
100k
points)

9.1k
views
gate20143
datastructure
binarysearchtree
numericalanswers
normal
+16
votes
2
answers
10
GATE201343
The preorder traversal sequence of a binary search tree is $30, 20, 10, 15, 25, 23, 39, 35, 42$. Which one of the following is the postorder traversal sequence of the same tree? $10, 20, 15, 23, 25, 35, 42, 39, 30$ $15, 10, 25, 23, 20, 42, 35, 39, 30$ $15, 20, 10, 23, 25, 42, 35, 39, 30$ $15, 10, 23, 25, 20, 35, 42, 39, 30$
asked
Sep 24, 2014
in
DS
by
Arjun
Veteran
(
418k
points)

2.1k
views
gate2013
datastructure
binarysearchtree
normal
+24
votes
4
answers
11
GATE20137
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? $O(1)$ $O(\log n)$ $O(n)$ $O(n \log n)$
asked
Sep 23, 2014
in
DS
by
Arjun
Veteran
(
418k
points)

2.9k
views
gate2013
datastructure
easy
binarysearchtree
+18
votes
3
answers
12
GATE200937,ISRODEC201755
What is the maximum height of any AVLtree with $7$ nodes? Assume that the height of a tree with a single node is $0$. $2$ $3$ $4$ $5$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

7.2k
views
gate2009
datastructure
binarysearchtree
normal
isrodec2017
+48
votes
7
answers
13
GATE200485
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $\Large \min \left ( \substack{\text{number of leafnodes}\\\text{in leftsubtree of $ ... worstcase time complexity of the program is? $\Theta (n)$ $\Theta (n \log n)$ $\Theta(n^2)$ $\Theta (n^2\log n)$
asked
Sep 19, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

7.9k
views
gate2004
binarysearchtree
normal
datastructure
+14
votes
6
answers
14
GATE20044, ISRO200926
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)? $2$ $3$ $4$ $6$
asked
Sep 19, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

4k
views
gate2004
datastructure
binarysearchtree
easy
isro2009
+28
votes
4
answers
15
GATE200363, ISRO200925
A data structure is required for storing a set of integers such that each of the following operations can be done in $O(\log n)$ time, where $n$ is the number of elements in the set. Deletion of the smallest element Insertion of an element if ... be used but not a heap Both balanced binary search tree and heap can be used Neither balanced search tree nor heap can be used
asked
Sep 17, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

5.1k
views
gate2003
datastructure
easy
isro2009
binarysearchtree
+15
votes
2
answers
16
GATE200319, ISRO200924
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 inorder traversal sequence of the resultant tree? $7 \ 5 \ 1 \ 0 \ 3 \ 2 \ 4 \ 6 \ 8 \ 9$ ... $9 \ 8 \ 6 \ 4 \ 2 \ 3 \ 0 \ 1 \ 5 \ 7$
asked
Sep 16, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

2.4k
views
gate2003
binarysearchtree
easy
isro2009
+45
votes
3
answers
17
GATE20036
Let $T(n)$ be the number of different binary search trees on $n$ distinct elements. Then $T(n) = \sum_{k=1}^{n} T(k1)T(x)$, where $x$ is $nk+1$ $nk$ $nk1$ $nk2$
asked
Sep 16, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

4.5k
views
gate2003
normal
binarysearchtree
+22
votes
3
answers
18
GATE200114
Insert the following keys one by one into a binary search tree in the order specified.$15, 32, 20, 9, 3, 25, 12, 1$Show the final binary search tree after the insertions. Draw the binary search tree after deleting $15$ from it. Complete the statements $S1$, $S2$ ... return 0; x = depth (t > left); S1: ___________; S2: if (x > y) return __________; S3: else return _______; }
asked
Sep 15, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

1.2k
views
gate2001
datastructure
binarysearchtree
normal
descriptive
+56
votes
5
answers
19
GATE200846
You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, 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? $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ None of the above, as the tree cannot be uniquely determined
asked
Sep 12, 2014
in
DS
by
Kathleen
Veteran
(
52.1k
points)

10.3k
views
gate2008
datastructure
binarysearchtree
normal
+29
votes
2
answers
20
GATE20125
The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is $\Theta(n\log n)$ $\Theta(n2^n)$ $\Theta(n)$ $\Theta(\log n)$
asked
Aug 5, 2014
in
DS
by
gatecse
Boss
(
16.2k
points)

2.9k
views
gate2012
datastructure
normal
binarysearchtree
Page:
« prev
1
2
3
4
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Previous Years Question Papers : ISI  MMA, PCB, DCG
Previous Years Question Papers : CMI  Computer Science
Minimum Number of States in a DFA accepting a binary number divisible by 'n'
GATE 2020 Application Form Opened!
My GATE Preparation Journey
Follow @csegate
Recent questions tagged binarysearchtree
Recent Blog Comments
Thanks for this post.
Thanks a ton for sharing this.
Thank you Arjun Sir.. Your blogs inspire a lot..
Feedback for next edition (if ever there's...
50,093
questions
55,328
answers
190,852
comments
86,255
users