Recent questions tagged binary-search-tree

1
Number of comparison made by algorithm that inserts values in the binary search tree?In the worst case for left or right skewed tree isn;t it o(n)?
2
While inserting an element into a BST, we will pass the element’s predecessor and successor (if they exist). (a) Ture (b) false (c) can't be determined.
3
What are dummies in Optimal binary Search Tree algorithm..? And is Cost calculated on the basis of Probability of Search keys only or On the basis of value on Search Element (At last it has to build a binary tree so it need to check on Values of Search Elements Also then why do we only consider probability whiile calculating Cost )..?? At last
4
Number of comparision in searching an element in a binary search tree is ?
1 vote
5
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values of in each node printed out the sequence of values obtained is 5,3,1,2,4,6,8,7. If the tree is traversed in post order, the sequence obtained would be A) 8 7 6 5 4 3 2 1 B) 1 2 3 4 8 7 6 5 C) 2 1 4 3 6 7 8 5 D) 2 1 4 3 7 8 6 5
6
what is the time complexity in creating a BInary search tree from an unsorted array??
7
The runtime for traversing all the nodes of a binary search tree with $n$ nodes and printing them in an order is $O(\lg n)$ $O(n \lg n)$ $O(n)$ $O(n^{2})$
8
Which of the following can be the sequence of nodes examined in binary search tree while searching for key $88$? $90, 40, 65, 50, 88$ $90, 110, 80, 85, 88$ $190, 60, 90, 85, 88$ $65, 140, 80, 70, 88$
9
Suppose we do not have a parent pointer in the nodes of a search tree, only left-child and right-child. Which of the following operations can be computed in time $O(\log n)$ for a balanced search tree? 1- find, insert, delete, but not min, max, pred, succ 2- find, insert, ... not pred, succ 3- find, insert, delete, pred, succ but not min, max 4- All of find, insert, delete, min, max, pred, succ
10
Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined? 925, 221, 912, 245, 899, 259, 363, 364 3, 400, 388, 220, 267, 383, 382, 279, 364 926, 203, 912, 241, 913, 246, 364 3, 253, 402, 399, 331, 345, 398, 364
1 vote
11
Suppose that we have numbers between $1$ and $1000$ in a binary search tree and we want to search for the number $365$. Which of the following sequences could not be the sequence of nodes examined ? $4, 254, 403, 400, 332, 346, 399, 365$ $926, 222, 913, 246, 900, 260, 364, 365$ $927, 204,913, 242, 914, 247, 365$ $4, 401, 389, 221, 268, 384, 383, 280, 365$
12
Given a binary search trees for a set of n=5 keys with the following probabilities: i 0 1 2 3 4 5 $p_i$ - 0.15 0.10 0.5 0.10 0.20 $q_i$ 0.05 0.10 0.05 0.05 0.05 0.10 The expected optimal cost of the search is 2.65 2.70 2.75 2.80
13
Consider the following binary search tree: If we remove the root node which of the node from the left subtree will be the new root? 11 12 13 16
1 vote
14
When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, ... by the user. A good data structure for accumulating the scores and ranking them is: a queue a heap a stack a binary search tree
1 vote
15
The tree given is as follows: 30 / \ 12 45 \ 18 Insert: 10,15,40,20,22 Which one of the following is the postorder traversal of the resultant tree? (A) 10,15,13,20,22,30,45,40,18 (B) 10,15,12,20,30,22,45,40,18 (C) 10,15,12,20,30,22,45,18,40 (D) None of these
16
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$.
17
Q). Find the number of trees that are possible .If we construct a binary search tree by successively inserting $5$ distinct items int an initially empty tree. a). $4$ b). $10$ c). $14$ d). $20$ I used the formula 2n!/(n+1)!*n!. Is it right ? also the ans given is 14,but I am getting 7.
1 vote
18
A binary search tree was constructed by inserting following elements into an initially empty binary tree. 50, 27, 16, 88, 34, 65, 52, 77, 93, 4, 12, 29, 44, 92 Preorder and postorder traversals of the resultant binary search tree were stored in arrays A and B ... of LCS present in these to array A and B ___________. Everything is ok here,, But not getting how length of LCS is calculated here.
19
20
I am stuck after JAN. It is not getting balanced even after 2 rotations. Can somebody help?
1 vote
21
When searching for the key value 50 in a binary search tree, node containing the key values 10, 30, 40, 70, 90, 120, 150, 175 are traversed, in any order. The number of different orders passing in which these keys values can occur on the search path from the root to node containing the value 50 are ________.
22
When searching for the key value 50 in a binary search tree, node containing the key values 10, 30, 40, 70, 90, 120, 150, 175 are traversed, in any order. The number of different orders passing in which these keys values can occur on the search path from the root to node containing the value 50 are ________.
23
Given preorder and postorder traversal of binary search tree. Preorder: 50, 27, 16, 4, 12, 34, 29, 44, 88, 65, 52, 77, 93, 92 Postorder: 12, 4, 16, 29, 44, 34, 27, 52, 77, 65, 92, 93, 88, 50 The number of nodes present at level 3 are _________. Assume root is present at level 0.
1 vote
24
25
Suppose there is a balanced binary search tree with $n$ nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node. Now, given two elements $a$ and $b$, such that $a < b$, we want to find the ... additions. $O(\log n)$ comparisons but a constant number of additions. $O(n)$ comparisons and $O(n)$ additions, using depth-first- search.
26
How many distinct binary search trees can be created out of 4 distinct keys? 5 14 24 35
27
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$
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