TAOCP 2.3.1 Exercise 16

Let `P` point to a node of a binary tree, and consider `Q = P*`, the successor of `NODE(P)` in preorder.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 16. [22] The diagrams in Fig. 24 help to provide an intuitive characterization of the position of NODE(Q$) in a binary tree, in terms of the structure near NODE(Q). If NODE(Q) has a nonempty right subtree, consider Q = $P, Q$ = P in the upper diagrams; NODE(Q$)

is the "leftmost" node of that right subtree. If NODE(Q) has an empty right subtree, consider Q = P in the lower diagrams; NODE(Q$) is located by proceeding upward in the tree until after the first upward step to the right.

Give a similar "intuitive" rule for finding the position of NODE(Q*) in a binary tree in terms of the structure near NODE(Q).

Verified: no
Solve time: 27s

Solution

Let P point to a node of a binary tree, and consider Q = P*, the successor of NODE(P) in preorder. By definition, a preorder traversal visits the root first, then the left subtree, then the right subtree. Thus the successor of NODE(P) is determined by whether P has a nonempty left subtree or not.

If LLINK(P) \ne \Lambda, the left subtree of P is nonempty. In preorder, we first visit NODE(P) and then immediately traverse its left subtree. Therefore Q = P* is simply the node pointed to by LLINK(P). In other words, NODE(Q) is the root of the left subtree of NODE(P).

If LLINK(P) = \Lambda, the left subtree is empty. In this case, preorder traversal proceeds from NODE(P) directly to the right subtree, if it exists. If RLINK(P) \ne \Lambda, then NODE(Q) is RLINK(P). Otherwise, if both LLINK(P) = \Lambda and RLINK(P) = \Lambda, the traversal must continue to the next node after NODE(P) in preorder, which is located by ascending the tree until after the first upward step from a left child to its parent. Formally, starting at P, move upward along parent links until reaching a node R such that the last move was from LLINK(R); then NODE(Q) is RLINK(R) if it exists, or continue upward until such a node is found. This is entirely analogous to the "empty right subtree" rule for Q$ in Fig. 24, but mirrored for the left child in preorder.

Thus the intuitive rule for finding NODE(Q*) can be stated as follows:

  1. If NODE(P) has a nonempty left subtree, NODE(Q*) is the root of that left subtree, i.e., LLINK(P).
  2. Otherwise, if NODE(P) has no left subtree but a nonempty right subtree, NODE(Q*) is the root of the right subtree, i.e., RLINK(P).
  3. If NODE(P) has neither left nor right subtree, ascend the tree until taking the first upward step from a left child; NODE(Q*) is then the right child of that ancestor, or continue ascending until such a node exists. If no such ancestor exists, Q* = LOC(T), the external pointer for the tree.

Equivalently, NODE(Q*) is the next node visited in preorder traversal, which is either the left child, if it exists, or the right child, or the first right child encountered while moving upward from a chain of nodes having no right children.

This completes the description of the intuitive rule. ∎