BinarySearchTree

What is the minimum number of nodes in a complete binary tree with height 3?

• 3

• 4

• 8

• 15

Answer explanation

A complete binary tree of height 3 has levels 0 to 3. The minimum number of nodes occurs when all levels are fully filled except possibly the last. Thus, the minimum is 2^3 = 8 nodes.

What is the maximum number of nodes in a complete binary tree with height 3?

• 3

• 8

• 15

• 31

Answer explanation

A complete binary tree of height 3 has levels 0 to 3. The maximum number of nodes is calculated as 2^(h+1) - 1, where h is the height. For h=3, it is 2^(3+1) - 1 = 15. Thus, the correct answer is 15.

We print the preorder traversal of BST of height h. Where the minimum element will appear?

• First

• Last

• Among the first h+1 elements

• Among the last h+1 elements

Answer explanation

In a preorder traversal of a BST, the root is visited first, followed by the left subtree and then the right subtree. The minimum element, being the leftmost node, will appear among the first h+1 elements.

Suppose we remove the root in the following tree. What will be the new root?

• 74

• 62

• 55

• 41

Answer explanation

When the root is removed, the new root is typically the largest value in the left subtree or the smallest in the right subtree. Here, 62 and 55 are valid candidates, with 62 being the largest in the left subtree.

Claim: It is possible that the following sequence is a preorder traversal in a BST? 24,15,12,4,17,20,13,32,37

• True

• False

Answer explanation

The sequence cannot be a preorder traversal of a BST because after 17, 20 should be less than 24 but greater than 17, which violates the BST property. Thus, the claim is False.