## Introduction

A tree whose elements have at most two children is called a binary tree. Considering the fact that every element in a binary tree can have only two children, we commonly name them the left and right child.

A Binary Tree node contains data, a pointer to the left child, and a pointer to the right child.

## Questions

**1. Consider an entire binary tree with 7 nodes. Let A denote the set of the first three elements obtained by acting Breadth-First search (BFS) starting from the root. Let B denote the set of the first three elements obtained by appearing depth-First search (DFS) starting from the root. The value of ∣A−B∣ is ___________.**

(A) 1

(B) 2

(C) 3

(D) 4

**Solution:** (A) 1

In the case of BFS, if we draw an entire binary tree, then in Set A, we have level1 + level2.

In DFS we have level1+ level 2 + level 3.

So A-B= remaining element of level 2.

**2. What will be the worst-case number of arithmetic operations finished by recursive binary search on a sorted array of length n?**

(A) Θ(√n)

(B) Θ(log2(n))

(C) Θ(n^{2})

(D) Θ(n)

**Solution:** (B) Θ(log2(n))

Arithmetic operations carried out by binary search on sorted data items means the computation of mid element required arithmetic operation. So it will likely be computed log(n) time.

**3. What is the worst-case time complexity of initially placing n ^{2} elements into an AVL tree with n elements?**

(A) Θ(n^{4})

(B) Θ(n^{2})

(C) Θ(n^{2} log n)

(D) Θ(n^{3})

**Solution:** (C) Θ(n^{2} log n)

1st insertion time complexity = O(log n)

2nd insertion time complexity = O(log(n+1))

3rd insertion time complexity = O(log(n+2))

.

.

.

n^{2}th insertion time complexity = O(log(n + n^{2}))

So, time complexity will be,

= O(log n) + O(log n+1)) + .... + O(log(n + n^{2}))

= O(log n*(n+1)*(n+2)*...(n+n^{2}))

= O(log nn^{2})

= O(n^{2} log n)

**4. A binary search tree wherein each non-leaf node has non-empty left, and right subtrees is a strictly binary tree. Any such tree with 19 leaves:**

(A) cannot have more than 37 nodes

(B) has exactly 37 nodes

(C) has exactly 35 nodes

(D) cannot have more than 35 nodes

**Solution:** (B) has exactly 37 nodes.

(2n-1) where n is the for the leaves nodes. So by that way, we've exactly 37 nodes.

**5. A full binary tree having n leaves contains**

(A) log 2n nodes

(B) n nodes

(C) 2n–1 node

(D) 2n nodes

**Solution:** (C) 2n-1 node

A full binary tree node has 0 or 2 children. We can say that a full binary tree is a binary tree in which all nodes except leaves have children. A full binary tree with n leaves consists of 2n – 1 node.

**6. A complete binary tree with the property that the value at every node is as least as large as the values at its children is called**

(A) binary search tree

(B) AVL tree

(C) completely balanced tree

(D) Heap

**Solution:** (D) Heap

In a Max. Binary Heap, the key-value at every node is as least as big as the values at its children. Further in Min Binary Heap, the key at root should be minimum among all keys present in Binary Heap.

**7. Which of the following various nodes can form a full binary tree?**

(A) 8

(B) 15

(C) 14

(D) 13

**Solution:** (B) 15

A binary tree in which nodes except leaves have children is known as a complete binary tree.

In a complete Binary, the number of leaf nodes is the number of internal nodes + 1.

**8. The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that block size is 1 kilobyte, the child pointer is 7 bytes long, and the search field value takes 14 bytes long. The order of the leaf node is ________.**

(A) 16

(B) 63

(C) 64

(D) 68

**Solution:** (A) 16

Given:

Key size = 14 bytes

Child pointer = 7 bytes

We assume the order of the B+ tree to be 'n'.

Block size >= (n - 1) * key size + n * child pointer

512 >= (n - 1) * 14 + n * 7

512 >= 14 * n - 14 + 7 * n

n <= (1024 + 14) / 20

n <= 1038 / 21

n <= 49.42

**9. A strictly binary tree with 10 leaves**

(A) cannot have more than 19 nodes

(B) has exactly 19 nodes

(C) has exactly 17 nodes

(D) has exactly 20 nodes

**Solution:** (B) has exactly 19 nodes.

A strict binary tree with n(i.e., 10) leaf nodes constantly has 2n-1(i.e., 19) intermediate nodes.

**10. The range of structurally different possible binary trees with 4 nodes is**

(A) 14

(B) 12

(C) 336

(D) 168

**Solution:** (A) 14

The total number of structurally different possible binary trees can be found using the Catalon number, which is (2n)!/ (n! *(n+1)!).

Now, n=4 implies the solution is 14.

**11. In a binary tree, the number of internal nodes of degree 1 is five, and the wide variety of inner nodes of degree 2 is 10. The variety of leaf nodes inside the binary tree is**

(A) 10

(B) 11

(C) 12

(D) 15

**Solution:** (B) 11

In a binary tree, the number of leaf nodes is continually 1 more than the number of internal nodes with 2 children.

So,

number of Leaf Nodes = number of internal nodes with 2 children + 1

number of Leaf Nodes = 10 + 1

number of Leaf Nodes = 11

**12. Consider a node in a Binary Tree. Given that X has two children permit Y to be Inorder successor of X. Which of the following is true about Y?**

(A) Y has no right child

(B) Y has no left child

(C) Y has both children

(D) None of the above

**Solution:** (B) Y has no left child

Since X has both children, Y needs to be the leftmost node in the right child of X.

**13. In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its descendant. What's the range of nodes inside the tree which have exactly one child?**

(A) 0

(B) 1

(C) (n-1)/2

(D) n-1

**Solution:** (A) 0

It is cited that every node has an odd number of descendants, including the node itself, so all nodes must have an even number of descendants 0, 2, 4 so on. this means that every node needs to have either zero or 2 children. So there can be no node with 1 child. Subsequently, 0 is a solution.

**14. The height of a tree is the length of the longest root-to-leaf path. The maximum and minimum number of nodes in a binary tree of height 5 is**

(A) 63 and 6, respectively

(B) 64 and 5, respectively

(C) 32 and 6, respectively

(D) 31 and 5, respectively

**Solution:** (A) 63 and 6, respectively

The number of nodes is maximum for a perfect binary tree.

A perfect binary tree of height h has 2^{h+1} - 1 node.

The number of nodes is minimum for a skewed binary tree.

A perfect binary tree of height h has h+1 nodes.

Must Read Recursive Binary Search.