Binary Heap MCQ Quiz - Objective Question with Answer for Binary Heap - Download Free PDF
Last updated on Apr 30, 2025
Latest Binary Heap MCQ Objective Questions
Binary Heap Question 1:
Let T(n) be the number of different binary search trees on n distinct elements-then
\(\mathrm{T}(\mathrm{n})=\sum_{\mathrm{k}=1}^{\mathrm{n}} T(K-1) T(x)\) where x is :
Answer (Detailed Solution Below)
Binary Heap Question 1 Detailed Solution
Let T(n) be the number of different binary search trees on n distinct elements. Then:
T(n) = ∑k=1n T(k-1) T(x) where x is:
- 1) n - k + 1
- 2) n - k
- 3) n - k - 1
- 4) n - k - 2
The correct answer is option 1: n - k + 1
Key Points
- The formula for the number of different binary search trees (BSTs) on n distinct elements can be understood as follows:
- For each element k (from 1 to n) chosen as the root, there are T(k-1) ways to arrange the elements to the left of k (i.e., the left subtree) and T(x) ways to arrange the elements to the right of k (i.e., the right subtree).
- In this context, x represents the number of elements remaining after choosing k and the elements to its left, which is n - k + 1.
- Thus, the formula is: T(n) = ∑k=1n T(k-1) T(n - k + 1).
Additional Information
- The number of different BSTs on n distinct elements is also known as the nth Catalan number, which has a closed-form expression: C(n) = (1 / (n + 1)) (2n choose n).
- This counting problem is fundamental in combinatorial mathematics and has applications in various fields, including computer science and algorithm design.
- Understanding the properties and formulas of BSTs helps in optimizing search and sort operations in data structures.
Binary Heap Question 2:
Consider a completely skewed (left/right) binary search tree with n elements. What is the worst case time complexity of searching an element in this tree?
Answer (Detailed Solution Below)
Binary Heap Question 2 Detailed Solution
Key Points
- A binary search tree (BST) is a binary tree where each node has a value greater than all the values in its left subtree and less than all the values in its right subtree.
- In a balanced BST, the time complexity for searching is O(log n) due to the tree's height being log(n).
- However, in a completely skewed (left or right) BST, the tree essentially behaves like a linked list.
- This means each node only has one child, and the tree's height becomes n (number of nodes).
- Therefore, the worst-case time complexity of searching an element in a completely skewed BST is O(n) because you may need to traverse all the nodes.
Important Points
- In a balanced BST, operations like insertion, deletion, and search have average time complexities of O(log n).
- In a completely skewed BST, these operations degrade to O(n) in the worst case.
Additional Information
- Self-balancing BSTs like AVL trees and Red-Black trees maintain their height close to log(n), ensuring efficient operations.
- Understanding the structure and properties of different types of BSTs is crucial for optimizing search operations in various applications.
Binary Heap Question 3:
How many distinct binary search trees can be created out of 4 distinct keys?
Answer (Detailed Solution Below)
Binary Heap Question 3 Detailed Solution
The correct answer is 14.
Key Points
- The number of distinct binary search trees (BSTs) that can be formed with 'n' distinct keys is given by the nth Catalan number.
- The nth Catalan number is calculated using the formula: C(n) = (2n)! / ((n+1)!n!)
- For n = 4, the Catalan number is C(4) = (2*4)! / ((4+1)!4!) = 8! / (5!4!) = (8*7*6*5*4*3*2*1) / ((5*4*3*2*1)*(4*3*2*1)) = 40320 / (120*24) = 40320 / 2880 = 14
- Hence, the number of distinct binary search trees that can be created out of 4 distinct keys is 14.
Additional Information
- The Catalan numbers appear in various counting problems in combinatorial mathematics, often involving recursively-defined objects.
- Other applications of Catalan numbers include counting the number of expressions containing n pairs of correctly matched parentheses, the number of ways to triangulate a polygon, and more.
- The first few Catalan numbers for n = 0, 1, 2, 3, 4 are 1, 1, 2, 5, and 14 respectively.
- The formula for the nth Catalan number can be derived from the binomial coefficients.
Binary Heap Question 4:
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?
Answer (Detailed Solution Below)
Binary Heap Question 4 Detailed Solution
The correct answer is Option 2: 11, 12, 10, 16, 19, 18, 20, 15.
Key Points
- The problem requires us to determine the postorder traversal of a binary search tree (BST) given its preorder traversal.
- In a BST, for any given node, all nodes in the left subtree are smaller, and all nodes in the right subtree are larger.
- Preorder traversal follows the sequence: Node -> Left Subtree -> Right Subtree.
- Postorder traversal follows the sequence: Left Subtree -> Right Subtree -> Node.
- Given preorder traversal: 15, 10, 12, 11, 20, 18, 16, 19, we can construct the BST and then find the postorder traversal.
Additional Information
- Constructing the BST from the given preorder traversal:
- 15 is the root node.
- 10 is the left child of 15.
- 12 is the right child of 10.
- 11 is the left child of 12.
- 20 is the right child of 15.
- 18 is the left child of 20.
- 16 is the left child of 18.
- 19 is the right child of 18.
- The constructed BST looks like this:
15 / \ 10 20 \ / 12 18 / / \ 11 16 19
- Now, performing postorder traversal on the constructed BST:
- Left Subtree of 10: 11, 12 (with 11 being the left child of 12)
- Right Subtree of 20: 16, 19, 18 (with 16 being the left child of 18 and 19 being the right child of 18)
- Combining the results: 11, 12, 10, 16, 19, 18, 20, 15
- Therefore, the correct postorder traversal is: 11, 12, 10, 16, 19, 18, 20, 15
Binary Heap Question 5:
In a binary search tree, which subtree of a node contains elements that are greater than the node’s value?
Answer (Detailed Solution Below)
Binary Heap Question 5 Detailed Solution
The correct answer is Right subtree.
Key Points
- A binary search tree (BST) is a data structure where each node has at most two children.
- Each node in a BST has a value, and the left subtree of a node contains only nodes with values less than the node’s value.
- The right subtree of a node contains only nodes with values greater than the node’s value.
- This property ensures that the tree remains ordered, making search operations efficient.
- For example, in a BST, if a node has a value of 10, all values in the right subtree of this node will be greater than 10.
Additional Information
- Binary search trees are widely used in computer science for efficient searching, insertion, and deletion operations.
- Balanced BSTs, such as AVL trees and Red-Black trees, ensure that the tree height remains logarithmic in the number of nodes, providing optimal performance.
- BSTs can be used to implement associative arrays, priority queues, and for sorting algorithms.
- Understanding the structure and properties of BSTs is fundamental for various advanced data structures and algorithms.
Top Binary Heap MCQ Objective Questions
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?
Answer (Detailed Solution Below)
Binary Heap Question 6 Detailed Solution
Download Solution PDFThe correct answer is "option 4".
CONCEPT:
A Binary Search Tree (BST) is also known as an ordered tree or sorted binary tree.
It is a binary tree with the following properties:
1. The left sub-tree of a node contains only nodes with key-value lesser than the node’s key value.
2. The right subtree of a node contains only nodes with a key-value greater than the node’s key value.
There are three types of traversal:
1. In-order traversal: In this traversal, the first left node will traverse, the root node then the right node will get traversed.
2. Pre-order traversal: In this traversal, the first root node will traverse, the left node then the right node will get traversed.
3. Post-order traversal: In this traversal, the First left node will traverse, the right node then the root node will get traversed.
The in-order traversal of the Binary search tree always returns key values in ascending order.
EXPLANATION:
The pre-order traversal of given BST is:
30, 20, 10, 15, 25, 23, 39, 35, 42.
So, the In-order traversal of the BST is:
10, 15, 20, 23, 25, 30, 35, 39, 42.
The Binary Search Tree is:
So the post-order traversal of the tree is:
15, 10, 23, 25, 20, 35, 42, 39, 30
Hence, the correct answer is "option 4".
Which of the following is/are correct in-order 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
Answer (Detailed Solution Below)
Binary Heap Question 7 Detailed Solution
Download Solution PDFStatement I: 3, 5, 7, 8, 15, 19, 25
It doesn't violate Binary search tree property and hence it is the correct order of traversal.
Statement II: 5, 8, 9, 12, 10, 15, 25
15 is left of 12 which violates binary search tree property.
Statement III: 2, 7, 10, 8, 14, 16, 20
14 is left of 10 which violates binary search tree property.
Statement IV: 4, 6, 7, 9 18, 20, 25
It doesn't violate Binary search tree property and hence it is the correct order of traversal.
Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i < = n), the index of the parent is:
Answer (Detailed Solution Below)
Binary Heap Question 8 Detailed Solution
Download Solution PDFThe correct answer is "option 3".
CONCEPT:
The binary heap is a complete binary tree with heap properties.
Binary heap is either max. heap (root value > all key values) or min. heap. (root value < all key values).
EXPLANATION:
Binary heap elements can be represented using an array with index value i (i < = n),
Parent node of element will be at index: floor (i / 2)
Left Child node will be at index: 2 * i
Right child node will be at index: 2 * i + 1
Hence, the index of the parent is floor (i / 2).
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
Answer (Detailed Solution Below)
Binary Heap Question 9 Detailed Solution
Download Solution PDFConcept:
Max heap: Root node value should be greater than child nodes.
Whenever we insert new element in heap, we will insert at the last level of heap.
After inserting element if max heap doesn’t follow the property then we will apply heapify algorithm until we get max heap.
Explanation:
Initial Heap
After inserting 1:
After inserting 7:
It doesn’t follow max heap property because 7 is greater than 5 so we will apply heapify algorithm on node 7.
After applied heapify algorithm:
Level order: 10, 8, 7, 3, 2, 1, 5
Hence option 1 is the correct answer.
What will be post order traversal of a binary Tree T, if preorder and inorder traversals of T are given by ABCDEF and BADCFE respectively?
Answer (Detailed Solution Below)
Binary Heap Question 10 Detailed Solution
Download Solution PDFThe correct answer is option 4.
Concept:
The given data,
preorder = ABCDEF
In order = BADCFE
Tree traversal | |||
Method Sequence | Inorder | Preorder | Postorder |
Left Sub-tree | Root | Left Sub-tree | |
Root | Left Sub-tree | Right Sub-tree | |
Right Sub-tree | Right Sub-tree | Root |
The binary tree for the traversal is,
Post order for the above tree is,
BDFECA
Hence the correct answer is BDFECA.
What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
Answer (Detailed Solution Below)
Binary Heap Question 11 Detailed Solution
Download Solution PDFConcept:
AVL tree is a height balanced binary search tree.
Insertion in AVL takes Θ (log n) time and height of an AVL tree with n nodes is log n.
Calculation:
The given AVL tree already has n nodes. Now each successive insertion would involve two operations: Θ(log n) to find the appropriate place to insert and another Θ(log n) to do any rotation if required. So in worst case, each successive insertion requires 2 log n operation i.e. Θ (log n).
Therefore, n2 insertions would require Θ (n2 log n).
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?
Answer (Detailed Solution Below)
Binary Heap Question 12 Detailed Solution
Download Solution PDFThe correct answer is option 1
Concept:
A binary search tree (BST) is a node-based binary tree data structure and it follows the following points
- Left sub-tree nodes key value will exist only if lesser than the parent node key value.
- Right sub-tree nodes key value will exist only if greater than the parent node key value.
- Left sub-tree and Right sub-tree must be a Binary search tree.
Explanation:
Step 1: First 10 comes and now that is the Root node.
Step 2: Now 1 came and 1 < 10 then insert Node 1 to the Left of Node 10.
Step 3: Now 3 came and 3 < 10 go to the Left of
Node 10 and check 3 > 1 then insert Node 3 to the Right of Node 1.
Step 4: Now 5 came and 5 < 10 go to the Left of
Node 10 and check 5 > 1 go to the Right of Node 1 then check 5 > 3 then insert Node 5 to the Right of Node 3.
Step 5: Now 15 came and 15 > 10 then insert Node 15 to the Right of Node 10.
Step 6: Now 12 came and 12 > 10 go to the Right of Node 10 and check 15 > 12 then insert Node 12 to the Left of Node 15.
Step 7: Now 16 came and 16 > 10 go to the Right of
10 and check 16 > 15 then insert 16 to the Right of Node 15.
After step 7, we can count the height of the tree as 3.
Important Points
Follow the longest path in the tree and count the edges that are height.
Tips To Learn:
Left sub-tree(key)<Node(key)<Right sub-tree(key)
Node(key): Parent node of Left sub-tree and Right sub-tree
Which of the following is a height of a given binary tree?
Hint:
The height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node.
Answer (Detailed Solution Below)
Binary Heap Question 13 Detailed Solution
Download Solution PDFThe correct answer is option 2.
Concept:
Binary tree:
A binary tree is a tree in which no node can have more than two children. Every binary tree has parents, children, siblings, leaves, and internal nodes.
Height of a binary tree:
The height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node.
Explanation:
Hence the correct answer is 2.
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
Answer (Detailed Solution Below) 509
Binary Heap Question 14 Detailed Solution
Download Solution PDFThe correct answer is 509.
Concept:
A binary search tree (BST) is a binary tree in which each node has a Comparable key (and an associated value) and the key in any node is greater than the keys in all nodes in that node's left subtree and less than the keys in all nodes in that node's right subtree.
Explanation:
The given data,
A binary search tree with 1000 different elements has been provided. The tree is also stored using the binary heap tree's array representation. The indices of an array begin with 0.
The index number of the first node at each level may be determined using (2h –1), where "h" is the tree's height. Also, the number of nodes at each level may be calculated using (2n –1), where n is the number of levels.
At 10th level number of nodes = 210-1 = 512.
At height 9, the index number of the first node = 29-1 = 511. Since the total number of nodes is 1000, we need to check the upper level. Because the rightmost number in the binary search tree is maximum.
At 9th level, no. of nodes = 29-1 = 256. At height 8, index no. of first node = 28-1 = 255 .
The index number of the last node in 9 th level, = 255 × 2 = 510
So the third largest value is stored at = 509
Hence the correct answer is 509.
The program written for binary search, calculates the midpoint of the span as mid : = (Low + High)/2. The program works well if the number of elements in the list is small (about 32,000) but it behaves abnormally when the number of elements is large. This can be avoided by performing the calculation as:
Answer (Detailed Solution Below)
Binary Heap Question 15 Detailed Solution
Download Solution PDFThe correct answer is option 1.
Key Points
- In a general scenario, binary search mid-value computed with, mid=(low+high)/2.
- However, with a vast list of elements, "high" would be a very large value. As a result, it's possible that it's beyond the Integer limit. It's known as an integer overflow.
- To stop this Integer overflow, the ‘mid' value can also be determined using, mid = (High - Low)/2 + Low
- Integer overflow is never an issue with this form.
Explanation
mid : = (High - Low)/2 + Low
mid : = High/2 - Low/2 + low
mid : = (High + Low)/2
Alternate Method
-
Option D is removed because it is the same as the incorrect option.
-
Taking into account The low index is 10, while the high index is 15.
-
Option B returns a mid-index of 3 that is not even in the sub-array index.
-
Choice C returns a mid-index of 2 that isn't even in the sub-array index.
-
Option A is the best solution.
Hence the correct answer is mid : = (High - Low)/2 + Low .