Consider the following binary tree: Determine the size, height, and width of the

Question

Consider the following binary tree:

Determine the size, height, and width of the tree.

Show the order the nodes will be visited in a:

i. preorder traversal ii. inorder traversal    iii. postorder traversal    iv. breadth-first traversal

(c) Identify all of the interior nodes and leaf nodes

(d) List all of the nodes on level 4.

(e) List all of the nodes in the path from root to each of the following nodes:

i. 4                                                              iv. 9

(f) Consider node 52 and list the node’s:

                 i. descendants                            ii. Ancestors                            iii. siblings

(g) Identify the depth of each of the following nodes:

                 i. 78                ii. 41                   iii. 60                     iv. 19

Explanation / Answer

Size of the tree is nothhing but the total number of nodes in the tree.
Theregore size = 13.
Height of the tree is nothing but the number of edges on the longest downward path between that root and a leaf.
Therefore height = 4.

(i) Preorder (Root, Left, Right) : 14,78,39,52,83,17,9,41,2,60,23,4,19
(ii) Inorder traversal (Left, Root, Right) : 39,78,17,83,9,52,41,14,60,2,4,23,19
(iii) Postorder (Left, Right, Root) : 39,17,9,83,41,52,78,60,4,19,23,2,14
(iv) breadth-first traversal: 14,78,2,39,52,60,23,83,41,4,19,17,9

c) Interior nodes:Internal node is the node that has at least one child. Otherwise it is a leaf node.

Interior nodes: 14,78,2,52,23,83
Leaf nodes: 30,60,4,19,17,9

d) Nodes in the Path from root to

i) 4

Path is 14-->2-->23-->4
Nodes are: 2,23

iv) 9

Path is 14-->78-->52-->83-->9
Nodes are: 78,52,83

(f) Consider node 52 and list the node’s:
i. descendants- descendant node is a node that is any node in the path from given node to the leaf node - 83,17
  
ii. Ancestors -ancestor node is a node that is any node in the path from given node to the root node - 78,14   
iii. siblings- nodes that are in same level- 39,60,23

g) The depth of a node is nothing but the number of edges from given node to the root.

i. 78 - 1
ii. 41- 3
iii.60- 2
iv. 19- 3

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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