Given the Binary Tree below: Answer the following questions (1 point each): a. W

Question

Given the Binary Tree below: Answer the following questions (1 point each): 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

(a.) Depth of the node holding the key value 18 = 4

Depth of the node is the total number of edges between root node and node for which we have to calculate depth.

(b.) Height of the tree = 7

Height of the tree is number of edges from root of the tree to the deepest leaf.

(c.) In this tree there are 24 internal nodes.

Internal node in a binary tree is a node having at least on child, i.e node which is not a leaf node.

(d.) In this tree there are 25 external nodes.

nodes having no child node is called external nodes or leaf nodes.

(e.) In pre order , nodes are visited in Root-Left-Right order , means firstly root node visited then Left subtree then right subtree ( Again in order Root Left Right ).

Here List of order of visit would be 50 32 7 4 29 18 40 36 43 56 84 60 58 57 59 82 63 61 75 83 94 87 92 97 .

(f.) As given tree is binary search tree( for any node, Left subtree value <Node and right subtree>=node) , So In order traversing results in non decreasing order. Here starting from the node holding the value 84 , List will be,

                         84 87 92 94 97.

(g.) In post order traversing First we visit Left subtree then right subtree, at last visit Root.

    Therefore Root will be visited lastly.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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