ADS 1

The height of a BT 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?

• 2 ^h-1 -1

• 2 ^h+1 -1

• 2 ^h +1

• 2 ^h-1 +1

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

• n

• n+1

• 2n

• 2n+1

Suppose a binary tree is constructed with n nodes, such that each node

has exactly either zero or two children. The maximum height of the tree

will be?

• (n+1)/2

• (n-1)/2

• n/2 -1

• (n+1)/2

Which of the following statement about binary tree is CORRECT?

• Every binary tree is either complete or full

• Every complete binary tree is also a full binary tree

• Every full binary tree is also a complete binary tree

• A binary tree cannot be both complete and full

In full binary search tree every internal node has exactly two children. If there are 100 leaf nodes in the tree, how many internal nodes are there in the tree?

• 25

• 49

• 99

• 101

Which type of traversal of binary search tree outputs the value in sorted order?

• Pre-order

• Post-order

• In-order

• None Answer B

In a full binary tree, every internal node has exactly two children. A full binary tree with 2n+1 nodes contains

• n leaf node

• n internal nodes

• n-1 leaf nodes

• n-1 internal nodes

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

• Pre-order successor

• In-order successor

• In-order predecessor

• Post-order successor

A binary search tree is generated by inserting in order the following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of the node in the left sub-tree and right sub-tree of the root, respectively, is

• (7, 4)

• (4, 7)

• (8, 3)

• (3, 8)

DFS Tree traversal is implemented using Stack.

• True

• False