QUESTION 03
What do the two links mean in left-child/right-sibling form?
2 marksAnswer
The left link identifies the first child; the right link identifies the next sibling. They are not both ordinary child links of the original tree.
QUESTION 04
Explain conversion of a general rooted tree to left-child/right-sibling representation.
5 marksAnswer in brief
A general rooted tree can be represented using at most two links per node without discarding its child order.
Conversion
- Preserve a chosen order among each node’s children.
- Use the left pointer for the first child.
- Connect that child’s right pointer to the next sibling, continuing across the sibling group.
- Represent missing first children or next siblings with NULL.
Example
Suppose A has children B, C and D, and B has child E. Set A.left = B, B.right = C and C.right = D. Set B.left = E. D.right is NULL. The original root has no next sibling, so A.right is NULL.
Interpretation
C is a sibling of B, not an original child of B. Reading both links as original parent-child relations would misinterpret the general tree. The transformed pointer arrangement is binary in representation, but its semantic link meanings must remain clear.
Advantages
A node needs two links regardless of how many children it has. There is no fixed child-array capacity to choose for every node. Iterating a node’s children means following the first-child link and then the sibling chain.
Complexity
Creating one representation node per original node and linking each relationship once takes O(n) structural work and O(n) representation storage. Traversing a node’s k children via siblings takes O(k). This conversion is not a numeric BST insertion or balancing operation.
Diagram or flowchart
