What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?
1 Crore+ students have signed up on EduRev. Have you? Download the App |
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? (GATE CS 2011)
How many distinct binary search trees can be created out of 4 distinct keys?
Which of the following traversal outputs the data in sorted order in a BST?
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
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)? (GATE CS 2004)
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?
Consider the following Binary Search Tree
Q.
If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?
Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder
Consider the following code snippet in C. The function print() receives root of a Binary Search Tree (BST) and a positive integer k as arguments.
// A BST node
struct node {
int data;
struct node *left, *right;
};
int count = 0;
void print(struct node *root, int k)
{
if (root != NULL && count <= k)
{
print(root->right, k);
count++;
if (count == k)
printf("%d ", root->data);
print(root->left, k);
}
}
Q. What is the output of print(root, 3) where root represent root of the following BST.
Consider the same code as given in above question. What does the function print() do in general? The function print() receives root of a Binary Search Tree (BST) and a positive integer k as arguments.
// A BST node
struct node {
int data;
struct node *left, *right;
};
int count = 0;
void print(struct node *root, int k)
{
if (root != NULL && count <= k)
{
print(root->right, k);
count++;
if (count == k)
printf("%d ", root->data);
print(root->left, k);
}
}
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?
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nalogb n + mclogd n), the value of a + 10b + 100c + 1000d is ____.
Let T(n) be the number of different binary search trees on n distinct elements. Then
where x is
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
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
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. [This question was originally a Fill-in-the-Blanks question]
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?
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?
55 docs|215 tests
|
55 docs|215 tests
|