TAOCP 2.3.1 Exercise 4

Section 2.3.1: Traversing Binary Trees

Exercise 4. [20] The text defines three basic orders for traversing a binary tree; another alternative would be to proceed in three steps as follows:

a) Visit the root,
b) traverse the right subtree,
c) traverse the left subtree,

using the same rule recursively on all nonempty subtrees. Does this new order bear any simple relation to the tree orders already discussed?

Verified: no
Solve time: 32s

Solution

Let us define the new traversal order recursively, as in the exercise:

Visit the root.
Traverse the right subtree in this order.
Traverse the left subtree in this order.

Call this traversal "root-right-left" or RRL for brevity. Let $T$ be a binary tree, and denote its left and right subtrees by $L$ and $R$, respectively, with root $A$; then the RRL sequence for $T$ is

$$ A ; \text{RRL}(R) ; \text{RRL}(L), $$

where $\text{RRL}(X)$ denotes the RRL traversal of subtree $X$.

Compare this to preorder traversal:

$$ \text{preorder}(T) = A ; \text{preorder}(L) ; \text{preorder}(R), $$

which visits the root first, then left subtree, then right subtree.

Observe that RRL traversal is precisely preorder traversal of the tree reflected about a vertical axis, because reflecting a tree exchanges left and right subtrees. Denote by $T^{\text{ref}}$ the reflection of $T$ obtained by swapping left and right children at every node. Then

$$ \text{RRL}(T) = \text{preorder}(T^{\text{ref}}). $$

Similarly, reflecting the tree and performing inorder traversal gives a sequence that is the reversal of the original symmetric order: if $T^{\text{ref}}$ is the reflection of $T$, then

$$ \text{inorder}(T^{\text{ref}}) = \text{reverse}(\text{inorder}(T)). $$

To justify this, consider that the inorder sequence visits the left subtree, then the root, then the right subtree. Reflecting swaps left and right, so the original right subtree is visited first, then the root, then the original left subtree, which is exactly the reversal of the original inorder sequence.

Similarly, postorder traversal of the reflected tree yields the reverse of the original postorder sequence:

$$ \text{postorder}(T^{\text{ref}}) = \text{reverse}(\text{postorder}(T)). $$

Hence the RRL traversal of $T$ has a simple relation to the standard orders: it is the preorder traversal of the reflected tree. In particular, it can also be obtained by reversing the order of the nodes in a mirrored preorder sequence.

To illustrate, let us apply RRL traversal to the example tree of equations (3)–(5). Let the original preorder sequence be

$$ A ; B ; D ; C ; E ; G ; F ; H ; J. $$

The mirrored tree exchanges left and right subtrees at each node; preorder of the mirrored tree yields the sequence

$$ A ; C ; F ; J ; H ; E ; B ; D ; G, $$

which is exactly the RRL sequence.

This establishes that the RRL traversal is preorder of the reflected tree, and therefore bears a simple and precise relation to the standard orders.

This completes the solution. ∎