If each node of an arbitrary tree contains 3 pointer fields: left-child, right-sibling, and parent, from any node in the tree, 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.
Question:
How to use only 2 pointers and 1 boolean value in each node so that the parent of a node or all of its children can be reached in time linear in the number of children.
(Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 217, Problem 10.4-6)
Answer:
Use 2 pointers left and right, where left always points to its leftmost child or NIL for leaves, and right generally points to right sibling but for rightmost node it points back to the parent. Then the boolean variable should record whether the node is rightmost or not. In this way, each parent node and its children form a loop in the tree (parent's left pointer and all children's right pointer), and they can be reached in time linear in the number of children.
clear explanation
ReplyDelete