Binary Heap MCQ Quiz - Objective Question with Answer for Binary Heap - Download Free PDF

Let T(n) be the number of different binary search trees on n distinct elements. Then:

T(n) = ∑_k=1ⁿ 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=1ⁿ 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.

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.

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.

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

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.

The 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".

Statement 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.

The 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).

Concept:

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.

The correct answer is option 4.

Concept:

The given data,

preorder = ABCDEF

In order = BADCFE

The binary tree for the traversal is,

Post order for the above tree is,

BDFECA

Hence the correct answer is BDFECA.

Concept:

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, n² insertions would require Θ (n² log n). 

The 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

1. Left sub-tree nodes key value will exist only if lesser than the parent node key value.
2. Right sub-tree nodes key value will exist only if greater than the parent node key value.
3. 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

The 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.

The 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 (2^h –1), where "h" is the tree's height. Also, the number of nodes at each level may be calculated using (2ⁿ –1), where n is the number of levels.

At 10th level number of nodes = 2^10-1 = 512.
At height 9, the index number of the first node = 2⁹-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 = 2^9-1 = 256. At height 8, index no. of first node = 2⁸-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 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 .