search
Log In

Recent questions tagged binary-search-tree

0 votes
0 answers
1
A binary search tree contains the values-$1,2,3,4,5,6,7$ and $8.$ The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output? $5\;\;3\;\;1\;\;2\;\;4\;\;7\;\;8\;\;6\;\;$ $5\;\;3\;\;1\;\;2\;\;6\;\;4\;\;9\;\;7$ $5\;\;3\;\;2\;\;4\;\;1\;\;6\;\;7\;\;8$ $5\;\;3\;\;1\;\;2\;\;4\;\;7\;\;6\;\;8$
asked Apr 1 in DS Lakshman Patel RJIT 69 views
0 votes
2 answers
2
0 votes
3 answers
3
If for a given Binary Search Tree (BST) the pre-order traversal is $41,23,11,31,62,50,73$. Then which of the following is its post-order traversal? $11,31,23,50,73,62,41$ $31,11,23,50,41,62,73$ $11,31,50,23,73,62,41$ $11,31,23,50,62,73,41$
asked Mar 30 in DS Lakshman Patel RJIT 145 views
0 votes
3 answers
4
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming. Breadth-first search cannot be used to find connected components of a graph. Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely. Depth-first-search can be used to find the connected components of a graph. a b c d
asked Mar 24 in Algorithms jothee 149 views
2 votes
5 answers
5
The preorder traversal of a binary search tree is $15, 10, 12, 11, 20, 18, 16, 19$. Which one of the following is the postorder traversal of the tree? $10,11,12,15,16,18,19,20$ $11,12,10,16,19,18,20,15$ $20,19,18,16,15,12,11,10$ $19,16,18,20,11,12,10,15$
asked Feb 12 in DS Arjun 3k views
3 votes
3 answers
6
What is the in-order successor of $15$ in the given binary search tree? $18$ $6$ $17$ $20$
asked Jan 13 in DS Satbir 260 views
1 vote
1 answer
7
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
asked Nov 20, 2019 in Algorithms KUSHAGRA गुप्ता 307 views
5 votes
3 answers
8
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node $A?$ $D$ $H$ $I$ $M$
asked Sep 13, 2019 in DS gatecse 257 views
0 votes
1 answer
9
here what to do first as FIZZA and IMRAN both are unbalanced than either to do RR rotation from FIZZA-IMRAN-NAVEEN or RL rotation from IMRAN-NAVEEN-LOVELY
asked Apr 13, 2019 in DS kd..... 116 views
0 votes
1 answer
10
Consider the following binary tree with root at level 0. What is the internal path length for the above tree? 31 14 29 32
asked Mar 10, 2019 in Algorithms s_dr_13 355 views
2 votes
4 answers
11
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?
asked Jan 16, 2019 in DS sripo 1.2k views
0 votes
0 answers
12
When searching for the key value 50 in a binary search tree, nodes containing the key values 10,15,20,30,60,80,89,90 are traversed, not necessarily in the given order. 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 50?
asked Jan 16, 2019 in DS Rishav Chetan 107 views
0 votes
1 answer
13
Can binary serach tree have duplicate elements in the tree?
asked Jan 12, 2019 in Programming akankshadewangan24 63 views
1 vote
1 answer
14
AVL tree is created by inserting the keys 2, 6, 1, 5, 3, 4, 7 in the given order (Assume the tree is initially empty). Then the level order traversals of the tree would be. 2, 1, 3, 5, 4, 6, 7 3, 2, 5, 1, 6, 4, 7 2, 1, 3, 4, 5 ... even after knowing all the concepts. After 2 or 3 rotations I get stuck trying to figure out which way to rotate. Please help me with the proper steps in this question.
asked Jan 6, 2019 in DS Gupta731 202 views
0 votes
1 answer
16
the number of binary search trees with 4 nodes (1 , 2 , 3 , 4) where 1 is always a leaf node?
asked Jan 1, 2019 in Programming Ashwani Yadav 131 views
0 votes
0 answers
17
Consider the following possible data structures for a set of n distinct integers. A min-heap An array of length sorted in increasing order A balanced binary search tree For which of these data structures, the number of steps needed to find and remove the 9th largest element in 0(logn) time in the worst case? I and III II and III I and II II only
asked Dec 21, 2018 in DS jatin khachane 1 110 views
0 votes
1 answer
18
Suppose we have a balanced BST and we run a program on the BST with n leaf nodes and compute the value of a function $g(x)$ for each node in BST. If the cost of computing $g(x)$ is minimum of number of leaf node in left subtree and number of leaf node in right subtree. The worst case time complexity of the program is: $O(n)$ $O(nlog_2n)$ $O(n^2)$ $O(n^2log_2n)$
asked Dec 18, 2018 in DS Gupta731 150 views
0 votes
1 answer
19
Consider the following routine bool do(struct node *root) { if(!root) return true; else if(( root ---> left != NULL && root ---> data < root ---> left---> data) ||(root-->right != NULL && root ---> data > root ----> right ----> data)) return false; else return (do( ... do(root---> right)); } What does they do() check whether a given tree is: $A)$ Max heap $B)$ Min Heap $C)$BST $D)$ Binary Tree
asked Nov 6, 2018 in DS Lakshman Patel RJIT 90 views
1 vote
0 answers
20
Consider an empty binary search tree of height $-1.$We need to fill the following sequence of numbers in it $: 11, 12, 13, 14, 15, 16, 17.$The number of ways in which the numbers can be inserted in an empty binary search tree, such that the resulting tree has height $6,$ is _____________ $A)2$ $B)4$ $C)32$ $D)64$
asked Oct 28, 2018 in Programming mitesh kumar 342 views
0 votes
0 answers
21
Consider a binary search tree for the following sequence of nodes $a,b,g,f,c,e,d$ What is the resultant tree if splaying is done at $'d'.$
asked Oct 28, 2018 in DS Lakshman Patel RJIT 126 views
0 votes
0 answers
22
Consider 4 labeled 1,2,3,4. The number of distinct binary tree possible such that whose inorder traversal is 1,2,3,4 are ........
asked Oct 20, 2018 in Programming Na462 157 views
0 votes
1 answer
23
what are the applications of optimal binary search tree?
asked Oct 1, 2018 in Algorithms aditi19 134 views
1 vote
1 answer
24
Consider the array $A=[20,13,19,8,3,5,4]$ that represents a heap. Draw the heap after removing the element $20.$ List all the distinct integer keys $k$ such that, when $k$ is inserted in the Binary Search Tree of Figure $1,$ its height increases. Note that you are not allowed to insert an already existing key again. Justify your answer.
asked Sep 18, 2018 in DS jothee 299 views
–1 vote
0 answers
25
0 votes
1 answer
27
Let T (n) be the number of comparisons needed in a binary search of a list of n elements. What is the recurrence relation? Explain. 1) T(n) = T(n/2) + 2 2) T(n) = T(n/2) + 1
asked Aug 29, 2018 in DS K ANKITH KUMAR 463 views
0 votes
1 answer
28
Consider following statements: S1: Rotation operation in AVL always preserves the Inorder ordering. S2: The median of all elements in AVL tree is always at root or one of its two children. S3: If every node in BST has either 0 or 2 children,then searching is O(logn) S4: In a 3 array tree. If number of internal node is 20 then number of Leaves are 41. True Statements ? Ans: Only S1 and S4
asked Aug 21, 2018 in DS Na462 818 views
0 votes
2 answers
29
What must be the ideal size of array if the height of tree is ‘l’? a) 2l-1 b) l-1 c) l d) 2l
asked Aug 19, 2018 in Programming pradeepchaudhary 534 views
0 votes
1 answer
30
8. What are the worst case and average case complexities of a binary search tree? a) O(n), O(n) b) O(logn), O(logn) c) O(logn), O(n) d) O(n), O(logn)
asked Aug 19, 2018 in Programming pradeepchaudhary 256 views
...