NAT1 mark
The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (*answer in integer*)
Numerical answer
MCQ2 marks
Let be the set of all integers from 1 to 15. Consider any order of insertion of the elements of into a binary search tree that creates a complete binary tree.
Which one of the following elements can NEVER be the third element that is inserted?
Single correct
NAT2 marks
The following sequence corresponds to the preorder traversal of a binary search tree :
The position of the element 60 in the postorder traversal of is ______. (*answer in integer*)
*Note:* The position begins with 1.
Numerical answer
MCQ1 mark
The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal.
T S
I: Inorder L: left subtree, node, right subtree
II: Preorder M: node, left subtree, right subtree
III: Postorder N: left subtree, right subtree, nodeSingle correct
MSQ2 marks
Consider a binary search tree (BST) with leaf nodes (). Given any node , the key present in the node is denoted as . All the keys present in the given BST are distinct. The keys belong to the set of real numbers.
For a node , let denote the node that is its inorder successor. If a node does not have an inorder successor, then is . As there are no duplicates, if is not , then .
Corresponding to every leaf node that has a non-NULL , a new key with the following property is to be inserted into the BST.
Let represent the list of all such new keys to be inserted into the BST.
Which of the following statements is/are true?
One or more correct
MSQ1 mark
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having distinct integers?
One or more correct
MCQ1 mark
Consider a binary tree in which every node has either zero or two children. Let be the number of nodes in .
Which ONE of the following is the number of nodes in that have exactly two children?
Single correct
NAT1 mark
Suppose the values 10, , 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let be the resulting binary search tree.
The number of edges in the path from the node containing 19 to the root node of is ___________. (Answer in integer)
Numerical answer
MCQ2 marks
You are given a set of distinct integers. A binary search tree is created by inserting all elements of one by one, starting with an empty tree. The tree follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into , and you do not have access to .
Which one of the following statements is TRUE?
Single correct
MCQ2 marks
Consider the C function foo and the binary tree shown.
typedef struct node {
int val;
struct node *left, *right;
} node;
int foo(node *p) {
int retval;
if (p == NULL)
return 0;
else {
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
}
Single correct
Answer key coming soon
NAT1 mark
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index __________
Numerical answer
Answer key coming soon
MCQ1 mark
A binary search tree contains distinct elements. What is the time complexity of picking an element in that is smaller than the maximum element in ?
Single correct
Answer key coming soon
NAT1 mark
Consider a complete binary tree with 7 nodes. Let denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
The value of is __________.
Numerical answer
Answer key coming soon
MCQ1 mark
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?
Single correct
Answer key coming soon
MCQ1 mark
What is the worst case time complexity of inserting elements into an AVL-tree with elements initially?
Single correct
Answer key coming soon
MCQ2 marks
In a balanced binary search tree with elements, what is the worst case time complexity of reporting all elements in range ? Assume that the number of reported elements is .
Single correct
Answer key coming soon
MCQ2 marks
Consider the following statements:
I. The smallest element in a max-heap is always at a leaf node
II. The second largest element in a max-heap is always a child of the root node
III. A max-heap can be constructed from a binary search tree in time
IV. A binary search tree can be constructed from a max-heap in time
Which of the above statements are TRUE?
Single correct
NAT2 marks
Let be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves and of are chosen uniformly and independently at random. The expected value of the distance between and in (i.e., the number of edges in the unique path between and ) is (rounded off to 2 decimal places) _____.
Numerical answer
NAT1 mark
The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _____.
Numerical answer
MCQ1 mark
Let be a binary search tree with 15 nodes. The minimum and maximum possible heights of are:
*Note: The height of a tree with a single node is 0.*
Single correct
Answer key coming soon
Use ← → to move