MCQ2 marks
The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
Single correct
Answer key coming soon
NAT1 mark
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex at a distance four from the root. If is the -th vertex in this BFS traversal, then the maximum possible value of is ________.
Numerical answer
Answer key coming soon
MCQ2 marks
Consider the following New-order strategy for traversing a binary tree:
• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:
Single correct
Answer key coming soon
NAT2 marks
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.*
Numerical answer
Answer key coming soon
MCQ1 mark
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
Single correct
MCQ1 mark
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9 18, 20, 25
Single correct
MCQ1 mark
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
Single correct
NAT1 mark
A binary tree T has 20 leaves. The number of nodes in T having two children is _____.
Numerical answer
NAT1 mark
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _____.
Numerical answer
MCQ1 mark
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
Single correct
NAT1 mark
Consider a rooted node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is . Then the value of is _____.
Numerical answer
NAT2 marks
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is _____.
Numerical answer
MCQ1 mark
Consider the following rooted tree with the vertex labeled P as the root:
The order in which the nodes are visited during an in-order traversal of the tree is
Single correct
NAT2 marks
Suppose we have a balanced binary search tree holding numbers. We are given two numbers and and wish to sum up all the numbers in that lie between and . Suppose there are such numbers in . If the tightest upper bound on the time to compute the sum is , the value of is _____.
Numerical answer
MCQ2 marks
Consider the pseudocode given below. The function
DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL) {
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}DoSomething, the value returned by the function corresponds to theSingle correct
MCQ1 mark
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of nodes?
Single correct
Answer key coming soon
MCQ2 marks
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?
Single correct
Answer key coming soon
MCQ1 mark
The worst case running time to search for an element in a balanced binary search tree with elements is
Single correct
Answer key coming soon
MCQ2 marks
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as
height(root) to compute the height of a binary tree rooted at the tree pointer root.
int height (treeptr n)
{ if (n == NULL) return -1;
if (n -> left == NULL)
if (n -> right == NULL) return 0;
else return [B1] ; // Box 1
else { h1 = height (n -> left);
if (n -> right == NULL) return (1+h1);
else { h2 = height (n -> right);
return [B2] ; // Box 2
}
}
}Single correct
Answer key coming soon
MCQ2 marks
We are given a set of distinct elements and an unlabeled binary tree with nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?
Single correct
Answer key coming soon
Previous pageUse ← → to move