TAOCP 2.3.1 Exercise 15
Let a node $P$ of a threaded binary tree be given.
Section 2.3.1: Traversing Binary Trees
Exercise 15. [15] In a threaded-tree representation like (10), each node except the list head has exactly one link pointing to it from above, namely the link from its parent. Some of the nodes also have links pointing to them from below; for example, the node containing C has two pointers coming up from below, while node E has just one. Is there any simple connection between the number of links pointing to a node and some other basic property of that node? (We need to know how many links point to a given node when we are changing the tree structure.)
Verified: no
Solve time: 41s
Solution
Let a node $P$ of a threaded binary tree be given. Every node except the list head has exactly one link from above, namely the ordinary link from its parent. Additional links pointing to $P$ may come from below, and these are necessarily threads.
We determine precisely how many thread links can point to $P$.
A left thread to $P$ occurs exactly when some node $Q$ has no left child and
$$ LLINK(Q)=$Q=P. $$
By the definition of threaded trees, this means that $P$ is the inorder predecessor of $Q$. Such a node $Q$ exists if and only if $P$ has no right child. Indeed, if $P$ has a right child, its inorder successor lies in its right subtree, so no node can have $P$ as inorder predecessor by means of a left thread. Conversely, if $P$ has no right child, its inorder successor $Q=P\�M1�RLINK(R)=R$=P.$$ Thus $P$ is the inorder successor of $R$. Such a node $R$ exists if and only if $P$ has no left child. If $P$ has a left child, its inorder predecessor lies in its left subtree, so no thread can point to $P$ from below on the right. If $P$ has no left child, its inorder predecessor $R=$P$ has no right child; otherwise a node in the right subtree of $R$ would lie between $R$ and $P$ in inorder. Therefore exactly one right thread points to $P$ when $P$ has no left child, and none otherwise. Consequently, the number of links pointing to $P$ is $$1 + \epsilon_L + \epsilon_R,$$ where $$\epsilon_L= \begin{cases} 1,&\text{if }P\text{ has no right child},\ 0,&\text{otherwise}, \end{cases} \qquad \epsilon_R= \begin{cases} 1,&\text{if }P\text{ has no left child},\ 0,&\text{otherwise}. \end{cases}$$ If $d(P)$ denotes the number of children of $P$, then $$\epsilon_L+\epsilon_R=2-d(P),$$ hence $$\boxed{\text{number of links pointing to }P = 3-d(P)}.$$ Thus a node with two children has one incoming link, a node with one child has two incoming links, and a leaf has three incoming links. This is the desired simple connection. ∎