Recent questions tagged binary-search-tree
Register

Recent questions tagged binary-search-tree

Recent questions tagged binary-search-tree
0 votes
0 answers 103 views
Gate CSE 2012
The worst case running time to search for an element in a balanced binary search tree with n2^n elements is A. Theta (nlogn) B. Theta (n2^n) C. Theta (n) D. Theta (logn) I am confused about the term balanced here because though we know about AVL ... AVL tree here? And ofcourse I am also curious to know how to solve this question. I will be grateful for your opinions. Regards, Ananya
Ananya Nayak asked in DS Jul 3, 2021
by Ananya Nayak
5 points
103 views
0 votes
0 answers 1.1k views
GATE CSE 2021 Set 1 | Question: 10 | Video Solution
Arjun asked in DS Feb 18, 2021
by Arjun
1.4k points
1.1k views
0 votes
0 answers 67 views
Binary Search Tree-Time complexity #Self-doubt
I have the following query: Given a sorted array, I know that we can construct a balanced BST in O(n) time. https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/ Suppose I have a sorted array -[1,2,3,4,5,6.....n]. I want to construct a ... , T(n)=T(n-1)+c.--->O(n). Am I wrong? Please explain in detail so I can understand. Thanks in advance.
loginofdeath asked in Algorithms Jul 25, 2020
by loginofdeath
5 points
67 views
0 votes
0 answers 33 views
GATE2016-2-40 Video Solution
The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is _________. Note: The height of a tree with a single node is $0$.
admin asked in DS Apr 18, 2020
by admin
589 points
33 views
0 votes
0 answers 66 views
GATE2007-IT-29 Video Solution
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$
admin asked in DS Apr 18, 2020
by admin
589 points
66 views
0 votes
0 answers 28 views
GATE2008-46 Video Solution
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 ... $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ None of the above, as the tree cannot be uniquely determined
admin asked in DS Apr 18, 2020
by admin
589 points
28 views
0 votes
0 answers 27 views
GATE2004-85 Video Solution
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 leaf-nodes}\\\text{in left-subtree of $ ... case time complexity of the program is? $\Theta (n)$ $\Theta (n \log n)$ $\Theta(n^2)$ $\Theta (n^2\log n)$
admin asked in DS Apr 18, 2020
by admin
589 points
27 views
0 votes
0 answers 18 views
GATE2009-37,ISRO-DEC2017-55 Video Solution
What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$. $2$ $3$ $4$ $5$
admin asked in DS Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 18 views
GATE1996-4 Video Solution
A binary search tree is used to locate the number $43$ ...
admin asked in DS Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 27 views
GATE2003-63, ISRO2009-25 Video Solution
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 ... used but not a heap Both balanced binary search tree and heap can be used Neither balanced search tree nor heap can be used
admin asked in DS Apr 18, 2020
by admin
589 points
27 views
0 votes
0 answers 19 views
GATE2003-6 Video Solution
Let $T(n)$ be the number of different binary search trees on $n$ distinct elements. Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is $n-k+1$ $n-k$ $n-k-1$ $n-k-2$
admin asked in DS Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 25 views
GATE2004-4, ISRO2009-26 Video Solution
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$
admin asked in DS Apr 18, 2020
by admin
589 points
25 views
0 votes
0 answers 20 views
GATE2006-IT-45 Video Solution
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\}$
admin asked in DS Apr 18, 2020
by admin
589 points
20 views
0 votes
0 answers 23 views
GATE2008-IT-71 Video Solution
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$ ... 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
admin asked in DS Apr 18, 2020
by admin
589 points
23 views
0 votes
0 answers 19 views
GATE2017-1-6 Video Solution
Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are: Note: The height of a tree with a single node is $0$. $4$ and $15$ respectively. $3$ and $14$ respectively. $4$ and $14$ respectively. $3$ and $15$ respectively.
admin asked in DS Apr 18, 2020
by admin
589 points
19 views
0 votes
0 answers 15 views
GATE2013-7 Video Solution
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)$
admin asked in DS Apr 18, 2020
by admin
589 points
15 views
0 votes
0 answers 25 views
GATE2012-5 Video Solution
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)$
admin asked in DS Apr 18, 2020
by admin
589 points
25 views
0 votes
0 answers 18 views
GATE2005-IT-12 Video Solution
The numbers $1, 2, .\dots n$ are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains $p$ nodes. The first number to be inserted in the tree must be $p$ $p + 1$ $n - p$ $n - p + 1$
admin asked in DS Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 16 views
GATE2017-2-36 Video Solution
The pre-order traversal of a binary search tree is given by $12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$. Then the post-order traversal of this tree is $2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$ $2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$ $7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12$ $7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12$
admin asked in DS Apr 18, 2020
by admin
589 points
16 views
0 votes
0 answers 15 views
GATE2005-IT-55 Video Solution
A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is $5, 3, 1, 2, 4, 6, 8, 7.$ ... $1, 2, 3, 4, 8, 7, 6, 5$ $2, 1, 4, 3, 6, 7, 8, 5$ $2, 1, 4, 3, 7, 8, 6, 5$
admin asked in DS Apr 18, 2020
by admin
589 points
15 views
0 votes
0 answers 43 views
GATE2003-19, ISRO2009-24 Video Solution
Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ ... $9 \ 8 \ 6 \ 4 \ 2 \ 3 \ 0 \ 1 \ 5 \ 7$
admin asked in DS Apr 18, 2020
by admin
589 points
43 views
0 votes
0 answers 15 views
GATE2015-1-23 Video Solution
What are the worst-case complexities of insertion and deletion of a key in a binary search tree? $\Theta(\log n)$ for both insertion and deletion $\Theta(n)$ for both insertion and deletion $\Theta(n)$ for insertion and $\Theta(\log n)$ for deletion $\Theta(\log n)$ for insertion and $\Theta(n)$ for deletion
admin asked in DS Apr 18, 2020
by admin
589 points
15 views
0 votes
0 answers 23 views
GATE1996-2.14 Video Solution
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)$
admin asked in DS Apr 18, 2020
by admin
589 points
23 views
0 votes
0 answers 10 views
GATE2013-43 Video Solution
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$
admin asked in DS Apr 18, 2020
by admin
589 points
10 views
0 votes
0 answers 15 views
GATE2008-IT-73 Video Solution
How many distinct BSTs can be constructed with $3$ distinct keys? $4$ $5$ $6$ $9$
admin asked in DS Apr 18, 2020
by admin
589 points
15 views
0 votes
0 answers 26 views
GATE2008-IT-12 Video Solution
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 ... 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)$
admin asked in DS Apr 18, 2020
by admin
589 points
26 views
0 votes
0 answers 16 views
GATE2015-1-10 Video Solution
Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)? $3, 5, 7, 8, 15, 19, 25$ $5, 8, 9, 12, 10, 15, 25$ $2, 7, 10, 8, 14, 16, 20$ $4, 6, 7, 9, 18, 20, 25$ I and IV only II and III only II and IV only II only
admin asked in DS Apr 18, 2020
by admin
589 points
16 views
0 votes
0 answers 14 views
GATE2008-IT-72 Video Solution
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$ ... 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
admin asked in DS Apr 18, 2020
by admin
589 points
14 views
0 votes
0 answers 23 views
GATE2015-3-13 Video Solution
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 $65$ $67$ $69$ $83$
admin asked in DS Apr 18, 2020
by admin
589 points
23 views
0 votes
0 answers 18 views
GATE2001-14 Video Solution
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$ ... ; x = depth (t -> left); S1: ___________; S2: if (x > y) return __________; S3: else return _______; }
admin asked in DS Apr 18, 2020
by admin
589 points
18 views
0 votes
0 answers 191 views
Testbook: Mock
In a BST, the key with value 5 was searched after traversing nodes with values 1,3,4,6,7,8,9, not necessarily in that order. What is the probability that the 3rd element on the search path beginning from the root is either 3 or 8?
Sambhrant Maurya asked in DS Jan 29, 2020
by Sambhrant Maurya
493 points
191 views
0 votes
0 answers 65 views
Binary Search Tree
Consider the following set of keys : [K,L,C,R,B,E,L,A,D]. In how many different order these keys can be inserted into BST such that the resultant tree looks like the below given tree:
zoboknows asked in Programming Jan 25, 2020
by zoboknows
5 points
65 views
0 votes
0 answers 123 views
Made Easy test series data structure binary search tree
Ram Swaroop asked in DS Jan 21, 2020
by Ram Swaroop
393 points
123 views
0 votes
0 answers 55 views
Cormen 3e BST Exercise-12.2-8 page no-294
Prove that no matter what node we start at in a height-h binary search tree, k successive calls to TREE-SUCCESSOR take O(k + h) time
aditi19 asked in DS Jan 3, 2020
by aditi19
59 points
55 views
0 votes
0 answers 55 views
Made Easy topic wise -2 algorithm bst
Consider the post order traversal of a binary search tree 1, 4, 3, 9, 13,7,6, 17, 20, 24, 18,15. The expected number of comparison when a randomly record is requested.(Upto 2 decimal place) Answer 3.16
Ram Swaroop asked in Algorithms Dec 22, 2019
by Ram Swaroop
393 points
55 views
To see more, click for the full list of questions or popular tags.
Ask a Question
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Developed by Chun