1.
The height of a BST is given as h. Consider the height of the tree as the no. of edges in the longest path from root to the leaf. The maximum no. of nodes possible in the tree is?

(a) 2h-1 -1
(b) 2h+1 -1
(c) 2h +1
(d) 2h-1 +1

(b) none

2.
The no of external nodes in a full binary tree with n internal nodes is?

(a) n
(b) n+1
(c) 2n
(d) 2n + 1

(b) An extended binary tree with n internal nodes has n+1 external nodes.

3.
The difference between the external path length and the internal path length of a binary tree with n internal nodes is?
(a) 1
(b) n
(c) n+1
(d) 2n

(d) The internal and external path lengths are related by

4.
Which of the following is a true about Binary Trees

(a) Every binary tree is either complete or full.

(b) Every complete binary tree is also a full binary tree
(c) Every full binary tree is also a complete binary tree
(d) None of the above

(d) A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

5.
A threaded binary tree is a binary tree in which every node that does not have right child has a thread to its

(a) Pre-order successor
(b) In-order successor
(c) In-order predecessor
(d) Post-order successor

(b)

6.
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is

(a) log2n

(b) n-1
(c) n
(d) 2n

(b)
A binary tree is a tree data structure in which each node has at most two child nodes.
The number of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1, or 2. The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.

7.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

(a) 7 5 1 0 3 2 4 6 8 9

(b) 0 2 4 3 1 6 5 9 8 7
(c) 0 1 2 3 4 5 6 7 8 9
(d) 9 8 6 4 2 3 0 1 5 7

(c)
Binary search tree – A binary tree in which the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than or equal to the parent.

8.
The in order and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The post order traversal of the binary tree is:

(a) d e b f g c a

(b) e d b g f c a
(c) e d b f g c a
(d) d e f g b c a

(c)
a
/ \
b c
/ \ / \
d e f g

9.
If a node having two children is to be deleted from binary search tree, it is replaced by its

(a) In-order predecessor

(b) In-order successor
(c) Pre-order predecessor
(d) None

(b) none

10.
A 2-3 is a tree such that
a) All internal nodes have either 2 or 3 children
b) All path from root to leaves have the same length

The number of internal nodes of a 2-3 tree having 9 leaves could be
(a) 4

(b) 5
(c) 6
(d) 7