Page 118 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 5: Trees

5.8 Self Assessment Notes

In the context of the figure given below give the answers of self assessment.

A

B C D

G H I E F

1. What is the degree of node E

(a) 3 (b) 2
(c) 1 (d) 0
2. What is the degree of node C
(a) 4 (b) 2
(c) 1 (d) 3

3. What is the level of node A
(a) 1 (b) 0
(c) 3 (d) 4
4. What is the level of node H
(a) 2 (b) 3

(c) 4 (d) 0
Fill in the blanks:
5. To delete a node from a binary search tree the method to be used depends on ......................
6. The order LDR is called ............................., the order LRD is called ...................... and the
order DLR is called ....................................
7. Binary tree is a special type of tree having degree ..............................
8. A degree three tree is called a ................................ tree.
9. A node with degree zero is called a ............................... node.

State the following statements are true or false:
10. A binary tree of depth k can have maximum 2k-1 number of nodes.
11. For a binary tree, maximum number of nodes at level i is 2*i-1.
12. A full binary tree is a binary of depth k having 2 − 1 nodes. If it has < 2 − 1, it is not a full
k
k
binary tree.
5.9 Review Questions

1. Give the array representation of a complete binary tree with depth k = 3, having the number
of nodes n = 7.

LOVELY PROFESSIONAL UNIVERSITY 113