TAOCP 2.3.1 Exercise 5

Section 2.3.1: Traversing Binary Trees

Exercise 5. [22] The nodes of a binary tree may be identified by a sequence of zeros and ones, in a notation analogous to "Dewey decimal notation" for trees, as follows: The root (if present) is represented by the sequence "1". Roots (if present) of the left and right subtrees of the node represented by \alpha are respectively represented by \alpha0 and \alpha1. For example, the node H in (1) would have the representation "1110". (See exercise 2.3-15.) Show that preorder, inorder, and postorder can be described conveniently in terms of this notation.

Verified: no
Solve time: 35s

---

Solution

Let the representation of a node be the binary string $\alpha$, where the root is represented by "1", the left child of $\alpha$ is $\alpha0$, and the right child is $\alpha1$.

The three traversal orders admit simple descriptions in terms of lexicographic relations on these binary strings.

For preorder, the root of a subtree is visited before either subtree. Thus, if $\alpha$ is the representation of a node, every descendant of $\alpha$ has the form $\alpha\beta$, where $\beta$ is a nonempty binary string; these descendants are visited after $\alpha$. Furthermore, the left subtree of $\alpha$, whose nodes begin with $\alpha0$, is traversed before the right subtree, whose nodes begin with $\alpha1$.

Hence preorder is obtained by arranging the node representations in lexicographic order, where shorter strings precede their extensions. In other words, $\alpha$ precedes $\beta$ if at the first place where they differ, $\alpha$ has $0$ and $\beta$ has $1$, or if $\alpha$ is a proper initial segment of $\beta$.

For example, in the tree of (1), the preorder sequence

$$ A\quad B\quad D\quad C\quad E\quad G\quad F\quad H\quad J \tag{3} $$

corresponds to

$$ 1,\ 10,\ 100,\ 11,\ 110,\ 1101,\ 111,\ 1110,\ 1111, $$

which are in lexicographic order.

For inorder (symmetric order), the left subtree precedes the root and the right subtree follows it. Thus, at a node $\alpha$, all nodes of the form $\alpha0\beta$ precede $\alpha$, and all nodes of the form $\alpha1\beta$ follow $\alpha$.

This order is described conveniently by regarding each representation as a binary fraction. Replace the initial digit "1" by the binary point, so that

$$ \alpha = 1a_1a_2\cdots a_k $$

corresponds to the binary fraction

$$ . a_1a_2\cdots a_k{}_2. $$

Then inorder is precisely the order of increasing numerical value of these fractions.

To verify this, suppose $\alpha$ corresponds to the fraction $x$. The left child $\alpha0$ corresponds to

$$ x-\frac{1}{2^{k+1}}, $$

and every node in the left subtree differs from $x$ by a negative amount less than $\frac{1}{2^k}$. Similarly, every node in the right subtree corresponds to a larger fraction. Therefore all nodes in the left subtree occur before $\alpha$, and all nodes in the right subtree occur after $\alpha$, exactly as required by the recursive definition of inorder traversal.

For the tree of (1), the representations are ordered in inorder as

$$ 100,\ 10,\ 1,\ 110,\ 1101,\ 11,\ 1110,\ 111,\ 1111, $$

which agrees with (4):

$$ D\quad B\quad A\quad E\quad G\quad C\quad H\quad F\quad J. \tag{4} $$

For postorder, both subtrees are traversed before the root. Therefore every descendant $\alpha\beta$ of $\alpha$ precedes $\alpha$, while the left subtree still precedes the right subtree.

Hence postorder is obtained by the same lexicographic ordering as preorder, except that whenever one representation is a proper initial segment of another, the longer string precedes the shorter. Equivalently, descendants precede ancestors, and among incomparable nodes the left subtree precedes the right subtree.

For the tree of (1), this gives

$$ 100,\ 10,\ 1101,\ 110,\ 1110,\ 1111,\ 111,\ 11,\ 1, $$

corresponding to (5):

$$ D\quad B\quad G\quad E\quad H\quad J\quad F\quad C\quad A. \tag{5} $$

Thus preorder, inorder, and postorder may be characterized as follows:

$$ \begin{aligned} \text{Preorder:} &\quad \text{lexicographic order};\[4pt] \text{Inorder:} &\quad \text{increasing order of associated binary fractions};\[4pt] \text{Postorder:} &\quad \text{lexicographic order with descendants preceding ancestors.} \end{aligned} $$

∎