Test: Trees- 1

QUESTION: 1

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

A.
log₂n
B.
n - 1
C.
n
D.
2ⁿ

Solution:

Because for 2 degree node, every time ‘2’ leafs are added and number of nodes increases is '1'. So number of nodes with degree 2 is always one less than number f leafs present in tree.

QUESTION: 2

Which of the following sequences denotes the post order traversal sequence of the tree of above question?

A.
fegcdba
B.
gcbdafe
C.
gcdbfea
D.
fedgcba

Solution:

QUESTION: 3

In the balanced binary tree in the figure given below, how many nodes will become unbalanced when a node is inserted as a child of the node "g”?

A.
1
B.
3
C.
7
D.
8

Solution:

When a node is added as a child of g.

Nodes a, b and c become unbalanced.

QUESTION: 4

A binary search tree is generated by inserting in order of the following integers: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. The number of nodes in the left subtree and right subtree of the root respectively is

A.
(4, 7)
B.
(7,4)
C.
(8,3)
D.
(3,8)

Solution:

The binary search tree is

The number of nodes in the left subtree and right subtree of the root respectively is (7, 4).

QUESTION: 5

A binary search tree contains the values 1,2,3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A.
53124786
B.
53126487
C.
53241678
D.
None of these

Solution:

(a) 53124786

6 can not be child of 8.
(b) 5312648

4 can not be child of 6.
(c) 53241678

1 can not be child of 4 or 5.

QUESTION: 6

Which of the following statements is false?

A.
A tree with n nodes has (n - 1) edges.
B.
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
C.
A complete binary tree with n internal nodes has (n + 1) leaves.
D.
The maximum number of nodes in a binary tree of height h is (^2h+1 - 1).

Solution:

A labelled rooted binary tree can not be constructed uniquely when inorder traversal is given along with post-order or pre-order traversal.

QUESTION: 7

A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

A.
x (n - 1) +1
B.
xn - 1
C.
xn + 1
D.
x(n + 1)

Solution:

In n-ary tree the total number of vertices are m = nx + 1
Where x: number of internal nodes and let l be the number of leaf nodes.
x + l = nx +1
l = (n - 1)x + 1
So number of leaf nodes in n-ary tree with x internal nodes is (n - 1) x + 1.

QUESTION: 8

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right subtrees, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

A.
(12(4567))
B.
(1((234) 56)7)
C.
(1(234) (567))
D.
(1(23NULL) (45))

Solution:

(1 (2 3 4) (5 6 7))

QUESTION: 9

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?