Clipboard Font Paragraph a. For each of the following trees, determine whether o

Question

Clipboard Font Paragraph a. For each of the following trees, determine whether or not the tree is a binary tree, a two-tree, full, and complete and give reasons for your determinations. If there is a subtree that does meet the criteria for the categories above, list the nodes of the subtree b. For each tree state: the height, the number of nodes, the number of external nodes, and the number of internal nodes. For trees I and Il perform a traversal of each of the following types: inorder, postorder, preorder, and level order c. 19 hnn 17 43 0 5 10 31 49 now 1S the for men of tirne a good party their to ad come

Explanation / Answer

Binary Tree: In binary tree the maximum degree of any node is at most two that means there may be zero degree node, one degree node and two degree node.

Full Binary Tree (Strictly Binary tree or 2-Tree): In full binary tree, each node is either a leaf or possesses exactly two children, which mean a node cannot have degree 1; it will have either 0 or 2.

Complete Binary Tree: In complete binary tree, if the levels except last are completely full, and the last level has its entire node to the left side.

Answer a):

From the above definitions, we can easily conclude that

Tree (i) is just binary tree, because node 4 and 8 has one right child, that does not satisfies the condition of full and complete binary tree.

Tree (ii) is fully bianry tree; because each node has either 0 or two children.

Tree (iii) does not come in any category as mentioned in the question.

Tree (iv) is binary tree; because of node in the tree have only one right child that is party.

Tree (i) contains a subtree that is full binary tree (19,17,43,31,49) and a binary tree (6,4,8,5,10) and a complete binary tree (43,31,49).

Tree (ii) contains a subtree that is full binary tree (-,a,/,b,c) and a complete binary tree (*,d,e), (/,b,c)

Tree (iii) contains a subtree that is complete binary tree (s,n,t) and one another complete bianry tree (n,f,r)

Tree (iv) contains a subtree that is full bianry tree (is,for,men,all,good,aid,come), a bianry tree (the, of,time,party,their,to), a full bianry tree (for,all,good,aid,come) and complete binary tree (all,aid,come), (time,their,to).

Answer b):

For tree (i): Height- 4; Number of nodes: 11; Number of internal nodes: 7; Number of external nodes: 4

For tree (ii): Height- 4; Number of nodes: 9; Number of internal nodes: 4; Number of external nodes: 5

For tree (iii): Height- 5; Number of nodes: 18; Number of internal nodes:10; Number of external nodes: 8

For tree (iv): Height- 5; Number of nodes: 14; Number of internal nodes: 7 Number of external nodes: 7

Answer c):

For tree (i) Inorder traversal: 4,5,6,8,10,11,17,19,31,43,49

Preorder traversal: 11,6,4,5,8,10,19,17,43,31,49

Postorder traversal: 5,4,10,8,6,17,31,49,43,19,11

Level order traversal: 11,6,19,4,8,17,43,5,10,31,49

For tree (ii) Inorder traversal: a - b / c + d * e

Preorder traversal: + - a / b c * d e

Postorder traversal: a b c / - d e * +

Level order traversal: + - * a / d e b c

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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