# Recent questions tagged binary-search-tree

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$
2
In binary search tree which traversal is used for getting ascending order values ? Inorder Preorder Postorder None of the options
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$
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
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$
6
What is the in-order successor of $15$ in the given binary search tree? $18$ $6$ $17$ $20$
1 vote
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.
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$
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
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
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?
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?
13
Can binary serach tree have duplicate elements in the tree?
1 vote
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.
15
16
the number of binary search trees with 4 nodes (1 , 2 , 3 , 4) where 1 is always a leaf node?
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
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)$
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
1 vote
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$
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'.$
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 ........
23
what are the applications of optimal binary search tree?
1 vote
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.
–1 vote
25
HOW TO SOLVE IT?
26
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