Answer the questions based on the binary trees: Observe the following binary tree and identify its…
Computer Science20255 marksShort answer
Answer the questions based on the binary trees:
(a)[2.0]
Observe the following binary tree and identify its type. Justify your answer.
Binary Tree (a)
(b)[2.0]
Observe the given tree and answer the following questions.
(i) Why can the following tree not be termed as a full binary tree?
(ii) What is the size of the given binary tree?
(iii) Name the internal nodes of the given binary tree.
Binary Tree (b)
(c)[1.0]
State any one condition for a balanced binary tree.
Answer
Answer (a)
AI
It is a complete binary tree. Every level is completely filled except possibly the last: level 0 has A, level 1 has B and C, level 2 has all 4 possible nodes D, E, F, G, and level 3 (the last, partially-filled level) has its nodes H, I, J packed as far left as possible (H and I under D, then J under E, with nothing under F or G).
Answer (b)
AI
(i) It is not a full binary tree because node C has only one child (E) instead of exactly 0 or 2 children; a full binary tree requires every node to have either zero or two children.
(ii) Size (total number of nodes) = 6 (A, B, C, F, D, E).
(iii) Internal nodes (nodes with at least one child) = A, B, C.
Answer (c)
AI
A binary tree is balanced if, for every node in the tree, the heights of its left and right subtrees differ by at most 1.
