Exercise 10.4.6

$\star$ The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers in each node: left-child, right-sibling, and parent. From any node, its parent can be reached and identified in constant time and all its children can be reached and identified in time linear in the number of children. Show how to use only two pointers and one boolean value in each node so that the parent of a node or all of its children can be reached and identified in time linear in the number of children.

The two pointers will be left-child and next. The boolean should be called last-sibling. Identifying the children is by starting with left-child and moving through next until the last sibling is reached. Identifying the parent is moving through next until the last sibling is reached and then moving through it once again.