Data Structure
Q51.
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?Q53.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 IV. 550,149,507,395,463,402,270 Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?Q54.
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,...,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?Q55.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 IV. 550,149,507,395,463,402,270 Which of the following statements is TRUE?Q57.
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?Q58.
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. If the tree is traversed in post-order, the sequence obtained would beQ59.
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?Q60.
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