TAOCP 2.3.3 Exercise 5
A triply linked tree contains, for each node $x$, three pointers: $PARENT(x)$ to the parent of $x$, $LCHILD(x)$ to the leftmost child of $x$, and $RLINK(x)$ to the next sibling of $x$.
Section 2.3.3: Other Representations of Trees
Exercise 5. [16] A triply linked tree, as shown in Fig. 26, contains PARENT, LCHILD, and RLINK fields in each node, with liberal use of Λ-links when there is no appropriate node to mention in the PARENT, LCHILD, or RLINK field. Would it be a good idea to extend this
representation to a threaded tree, by putting "thread" links in place of the null LCHILD and RLINK entries, as we did in Section 2.3.1?
Verified: yes
Solve time: 1m05s
Solution
A triply linked tree contains, for each node $x$, three pointers: $PARENT(x)$ to the parent of $x$, $LCHILD(x)$ to the leftmost child of $x$, and $RLINK(x)$ to the next sibling of $x$. By definition, $LCHILD(x) = \Lambda$ if $x$ has no children, and $RLINK(x) = \Lambda$ if $x$ is the last child of its parent. Similarly, $PARENT(x) = \Lambda$ if $x$ is a root. The question asks whether it is advisable to extend this representation to a threaded tree by replacing the null $LCHILD$ and $RLINK$ pointers with threads, as in Section 2.3.1.
In a standard threaded tree, the null $LLINK$ and $RLINK$ fields are replaced by pointers to the in-order predecessor or successor of the node. These threads allow one to traverse the tree efficiently in preorder, inorder, or postorder without using a stack or recursion. The fundamental property of threads is that they provide an unambiguous path through the tree even when no children or siblings exist.
Consider a triply linked tree with a threading scheme applied to $LCHILD$ and $RLINK$. Each $LCHILD(x) = \Lambda$ would now point to some node $y$ that would be the preorder successor if $x$ had no left child, and each $RLINK(x) = \Lambda$ would point to the next node in the appropriate traversal if $x$ had no right sibling. The complication arises because the triply linked tree already encodes three independent types of relationships: upward, leftmost child, and next sibling. The standard threading mechanism relies on a tree with only two fields per node (left and right) and a clear notion of inorder or preorder traversal based solely on these two links. In the triply linked case, $PARENT$ is independent of $LCHILD$ and $RLINK$, so replacing null child or sibling pointers with threads creates ambiguity: it is no longer clear whether a pointer represents an actual child, a sibling, or a traversal thread, unless additional tagging is introduced.
Moreover, threaded trees are most beneficial when traversal in a particular order is frequent and when stackless or recursive-free algorithms are desired. In a triply linked tree, upward traversal is already trivial via $PARENT$, and downward traversal through children is trivial via $LCHILD$ and $RLINK$. Stackless traversal is possible without threading by using $PARENT$ pointers: to visit the next node in preorder, one moves to $LCHILD(x)$ if it exists; otherwise, repeatedly follow $RLINK$ or $PARENT$ until a nonnull $RLINK$ is found, then proceed to that node. Thus the primary advantage of threading is already achievable using the $PARENT$ links without introducing threads.
Adding threads in place of null $LCHILD$ and $RLINK$ fields would therefore increase the complexity of the data structure without a proportional benefit. Each node would require careful tagging to distinguish between actual child/sibling links and threads. The resulting representation would be more difficult to maintain and less transparent, while offering negligible improvement in traversal efficiency, since the $PARENT$ field already enables upward and left-to-right navigation efficiently.
Consequently, it is not a good idea to extend a triply linked tree to a threaded tree in this manner. The existing triply linked structure suffices for efficient traversal, and threading would introduce unnecessary complexity.
This completes the proof.
∎