Given the Binary Tree below: a. What is the depth of node holding key value 18?

Question

Given the Binary Tree below:

a. What is the depth of node holding key value 18?

b. Determine the height of the tree.

c. How many internal nodes are there in this tree?

d. How many external nodes are there in this tree?

e. List the “order of visit” resulting from a Pre-Order Traversal method starting from the Root node.

f. List the “order of visit” resulting from an In-Order Traversal method starting from the node holding the key value 84.

g. List the “order of visit” resulting from a Post-Order Traversal method starting from the Root node.

Explanation / Answer

Given the Binary Tree below:
a. What is the depth of node holding key value 18?
The depth of a node is the number of edges from the root to the node.
So, the depth of node holding key value 18 is: 4.

b. Determine the height of the tree.
The height of a tree is the number of edges from the root to the deepest leaf.
So, the one of the deepest leaf is: 61. And the number of edges from root to that
leaf is: 6. Note that, here the leaf(dummy) nodes are not considered. If you wish
to consider those as well, the height will become 7.

c. How many internal nodes are there in this tree?
An internal node is the one which doesn't have a leaf. In this figure,
the nodes in Blue colored are the leaf nodes, and all the remaining are internal nodes.
So, the number of internal nodes are: 24.
If you consider the blue nodes as dummy, and the just previous to those are leaf nodes,
then the number of internal nodes are: 13.

d. How many external nodes are there in this tree?
With reference to previous answer: the leaf nodes are the external nodes.
If blue colored nodes are considered leaves, there are total of 25 external nodes.
If considered the other way, the number of external nodes is: 11.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.