TAOCP 2.3.1 Exercise 35

Section 2.3.1: Traversing Binary Trees

Exercise 35. [40] Define a ternary tree (and, more generally, a t-ary tree for any t \ge 2) in a manner analogous to our definition of a binary tree, and explore the topics discussed in this section (including topics found in the exercises above) that can be generalized to t-ary trees in a meaningful way.

Verified: no
Solve time: 47s

Setup

A ternary tree is defined recursively as either empty, or consisting of a root together with three ordered ternary subtrees, called the first, second, and third subtrees. More generally, for any fixed integer $t\ge2$, a $t$-ary tree is either empty, or consists of a root together with $t$ ordered $t$-ary subtrees.

Let

$$ \operatorname{CHILD}_1(P),\operatorname{CHILD}_2(P),\ldots,\operatorname{CHILD}_t(P) $$

denote the links from a node $P$ to its $t$ subtrees, with value $\Lambda$ when the corresponding subtree is empty.

The purpose of the exercise is to determine which notions of Section 2.3.1 extend naturally to $t$-ary trees, and to formulate the corresponding algorithms and representations.

Solution

The fundamental concepts of traversal extend immediately.

For a nonempty $t$-ary tree with root $R$, preorder traversal is defined by

Visit $R$.
Traverse the first subtree.
Traverse the second subtree.
Continue similarly through the $t$th subtree.

Postorder traversal is defined by

Traverse the first subtree.
Traverse the second subtree.
Continue similarly through the $t$th subtree.
Visit $R$.

There is no unique analogue of inorder when $t>2$, because the root can no longer be placed uniquely between two groups of subtrees. A meaningful generalization is obtained by fixing an integer $k$ satisfying

$$ 1\le k\le t. $$

The $k$th symmetric order is then defined recursively by

Traverse subtrees $1,\ldots,k-1$.
Visit the root.
Traverse subtrees $k,\ldots,t$.

For $t=2$ and $k=2$, this reduces to ordinary inorder traversal.

The proof of correctness of traversal algorithms proceeds exactly as for Algorithm T. The stack contains ancestors whose remaining subtrees have not yet been processed. Induction on the number of nodes establishes correctness.

To traverse a $t$-ary tree in the $k$th symmetric order, each stack entry must contain not only a node address but also an index indicating which subtree is to be processed next. Thus an entry has the form

$$ (P,i), $$

where $0\le i\le t$.

The interpretation is that subtrees $1,\ldots,i$ have already been processed.

When a node is first encountered, $(P,0)$ is pushed. Whenever the algorithm returns to that node, the index is increased. If $i=k-1$, the node is visited before processing subtree $k$; otherwise the next subtree is processed. After subtree $t$ has been traversed, the stack entry is removed. The same inductive argument used for Algorithm T proves that every node is visited exactly once and in the prescribed order.

The successor and predecessor notation of (6) also generalizes. If a traversal order has been specified, define

$$ P^*=\text{successor of }NODE(P)\text{ in preorder}, $$

$$ P^#=\text{successor of }NODE(P)\text{ in postorder}, $$

and similarly for predecessors. For a chosen symmetric order, define

$$ P$=\text{successor of }NODE(P)\text{ in that symmetric order}, $$

$$ $P=\text{predecessor of }NODE(P)\text{ in that symmetric order}. $$

The identities

$$ (P^)=(P)^=P, $$

$$ #(P^#)=(#P)^#=P, $$

$$ $(P$)=($P)$=P $$

remain valid whenever the corresponding successor and predecessor exist.

Threaded representations also extend naturally. Fix a symmetric order. Every null child link may be replaced by a thread to the predecessor or successor in that order.

For a $t$-ary tree, each node requires $t$ link fields

$$ \operatorname{CHILD}_1,\ldots,\operatorname{CHILD}_t, $$

together with $t$ tag bits

$$ \operatorname{TAG}_1,\ldots,\operatorname{TAG}_t. $$

The interpretation is

$$ \operatorname{TAG}_i(P)=0 \quad\Longleftrightarrow\quad \operatorname{CHILD}_i(P) $$

is an ordinary subtree link, while

$$ \operatorname{TAG}_i(P)=1 $$

indicates that the field contains a thread.

The binary threaded-tree idea corresponds to the special case $t=2$.

The analogue of Algorithm S is immediate. Suppose that a node $P$ has a thread field leading directly to its successor in the chosen order. Then the successor is obtained in constant time whenever the corresponding tag equals $1$. Otherwise the algorithm enters the appropriate subtree and follows ordinary links until reaching the first node of that subtree in the traversal order. The correctness argument is identical to that of Algorithm S.

Exercise 32 generalizes by storing explicit successor and predecessor fields. Each node contains

$$ \operatorname{SUC}(P)=P$, \qquad \operatorname{PRED}(P)=$P. $$

Insertion of a new node requires updating only the predecessor-successor chain near the insertion point. The local modifications are independent of the number of children and therefore extend directly from binary trees to $t$-ary trees.

Exercise 33 also generalizes. One may store, for example, preorder successor links explicitly:

$$ \operatorname{NEXT}(P)=P^*, $$

together with ordinary child links. Insertion and copying algorithms must preserve the preorder chain. Since preorder is defined for every $t$-ary tree exactly as for binary trees, the required updates remain local and are handled by adjusting the predecessor and successor of the inserted node in the preorder sequence.

Exercise 34 generalizes as well. To detach a subtree rooted at $P$, one disconnects the parent link leading to $P$ and replaces it by the appropriate thread or null value. To attach the subtree elsewhere, one redirects the chosen child field of the new parent and repairs the affected thread structure. The operation depends only on the local neighborhood of the attachment and detachment points, not on the number of possible child positions.

The counting properties of binary trees also have $t$-ary analogues. Let a finite $t$-ary tree contain $n$ nodes. Each node contributes $t$ child fields, hence there are $tn$ child fields altogether. Since every node except the root is reached by exactly one nonnull child link, the number of nonnull child links is

$$ n-1. $$

Therefore the number of null child links equals

$$ tn-(n-1) =(t-1)n+1. $$

For $t=2$ this becomes

$$ n+1, $$

which is the binary-tree result underlying threaded representations.

Verification

A traversal definition must satisfy two conditions: every node is visited exactly once, and the order is recursively determined by the root and its subtrees.

Preorder satisfies these conditions because the root is visited first and each subtree is then traversed recursively.

Postorder satisfies these conditions because each subtree is traversed recursively before the root is visited.

The $k$th symmetric order satisfies these conditions because the root is visited exactly once, after the first $k-1$ subtrees and before the remaining subtrees. When $t=2$ and $k=2$, the definition becomes

Traverse the left subtree.
Visit the root.
Traverse the right subtree,

which is exactly inorder traversal.

For the null-link count, there are $tn$ child fields and exactly $n-1$ nonnull links. Subtracting yields

$$ (t-1)n+1 $$

null links. Hence a threaded representation has precisely $(t-1)n+1$ opportunities for replacing null links by threads.

Notes

The binary case is distinguished by the existence of a unique symmetric order. For $t>2$, several inequivalent symmetric orders are possible, depending on the chosen position of the root among the $t$ subtrees.

Preorder, postorder, successor-predecessor notation, stack-based traversals, threaded representations, insertion algorithms based on traversal links, copying algorithms, and subtree-detachment operations all extend naturally to $t$-ary trees. The principal modification is that each node must carry information concerning which of its $t$ subtrees is currently being processed.