# 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, andparent. 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.