Past exam question: 2062 Baishakh (Regular / Back), Q4(b)
Open in the Padhaiko appQuestion
Is the given tree in figure is strictly binary tree? Give reason. What is the depth of the given tree? Write the sequences of node in preorder, postorder and inorder traversal.
[figure: binary tree rooted at A; A has left child B and right child E; B has left child C and right child D; E has left child F and right child G; F has left child H and right child I]
Solution
1. Is It a Strictly Binary Tree? Yes. A strictly binary tree (full binary tree) is a binary tree in which every node has either children (leaf) or children (internal node). Here:
- Internal nodes
A (B, E),B (C, D),E (F, G),F (H, I)all have exactly 2 children. - Leaf nodes
C, D, G, H, Iall have 0 children.
No node has only 1 child, so it is a strictly binary tree.
2. Depth (Height) of the Tree:
- Root
Ais at level0;B, Eat level1;C, D, F, Gat level2;H, Iat level3. - Longest path from root
Ato leaf (A -> E -> F -> HorI) has edges (or levels/nodes if 1-indexed depth). Thus depth (max level , 4 levels).
3. Traversals:
- Preorder (
Root -> Left -> Right):A, B, C, D, E, F, H, I, G - Postorder (
Left -> Right -> Root):C, D, B, H, I, F, G, E, A - Inorder (
Left -> Root -> Right):C, B, D, A, H, F, I, E, G
Answer:
- Strictly Binary Tree? Yes, every node has either 0 or 2 children.
- Depth: (levels to ; 4 node levels).
- Preorder:
A, B, C, D, E, F, H, I, G| Postorder:C, D, B, H, I, F, G, E, A| Inorder:C, B, D, A, H, F, I, E, G.