Q6➡| 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?
i ➥ 5 3 1 2 4 7 8 6
ii ➥ 5 3 1 2 6 4 8 7
iii ➥ 5 3 2 4 1 6 7 8
iv ➥ 5 3 1 2 4 7 6 8
Q7➡| Which of the following statement is false?
i ➥ A tree with n nodes has (n-1) edges.
ii ➥ A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
iii ➥ A complete binary tree with n internal nodes has (n+1) leaves.
iv ➥ The maximum number of nodes in a binary tree of height h is 2h+1 -1.
Q8➡| 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
i ➥ x(n−1)+1
ii ➥ xn−1
iii ➥ xn+1
iv ➥ x(n+1)
Q9➡| Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
i ➥ (1 2 (4 5 6 7))
ii ➥ (1 (2 3 4) 5 6) 7)
iii ➥ (1 (2 3 4)(5 6 7))
iv ➥ (1 (2 3 NULL) (4 5))
Q10➡| 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?
6,iv
7, ii
8, i
9, i
10, i
6: iv
7: iii
9: ii does not
10: ii