Question

40. Consider the following tree: 48 29 81 14 37 67 88 17 55 85 97 N Figure 7 a) (1 mark) What is the height of this tree? b) (1 mark) What is the level of the node containing "17"? c) (1 mark) What is the value contained in this tree's root node? d) (1 mark) What are the ancestors of the node containing "81"? e) (1 mark) How many leaf nodes are contained in this tree? f) (1 mark) What is the degree of the node containing "67"? g) (1 mark) What is the degree of this tree? h) (1 mark) Trace out the pre-order traversal of this tree. i) (1 mark) Trace out the in-order traversal of this tree. j) (1 mark) Trace out the post-order traversal of this tree. k) (1 mark) Trace out the level-order traversal of this tree.

Answer 1

a) What is the height of this tree?

Answer: the height of this tree is 3. Because Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node. Height of a tree is the height of root node.

b) What is the level of the node containing “17”?

Answer: The level of the node containing “17” is 3. Each step from top to bottom is called as level of a tree. The level count starts with 0 and increments by 1 at each level or step.

c) What is the value contained in this tree’s root node?

Answer: The value contained in this tree’s root node is 48.

d) What are the ancestors of the node containing “81”?

Answer: the ancestors of the node containing “81” is only 48.

e) How many leaf nodes are contained in this tree?

Answer: 6 lead nodes are contained in this tree and these are 2, 17, 37, 55, 85 and 97.

f) What is the degree of the node containing “67”?

Answer: the degree of the node containing “67” is 1 because it has only one child node that is 55.

g) What is the degree of this tree?

Answer: the degree of this tree is 2 because Degree of a tree is the highest degree of a node among all the nodes in the tree.

h) Trace out the pre order traversal of this tree.  

Answer: Pre order traversal (Root, Left and Right). The pre order traversal of this tree is 48, 29, 14, 2, 17, 37, 81, 67, 55, 88, 85 and 97.

i) Trace out the in order traversal of this tree.  

Answer: In order traversal (Left, Root and Right). The in order traversal of this tree is 2, 14, 17, 29, 37, 48, 55, 67, 81, 85, 88 and 97.

j) Trace out the post order traversal of this tree.  

Answer: Post order traversal (Left, Right and Root). The post order traversal of this tree is 2, 17, 14, 37, 29, 55, 67, 85, 97, 88, 81 and 48.

k) Trace out the level order traversal of this tree.  

Answer: level order traversal (print the same level node from root to leaf). The level order traversal of this tree is 48, 29, 81, 14, 37, 67, 88, 2, 17, 55, 85, and 97.