TAOCP 2.3.1 Exercise 6
Let a binary tree have $n$ nodes, with preorder sequence u_1 u_2 \dots u_n and inorder sequence
Section 2.3.1: Traversing Binary Trees
Exercise 6. [M22] Suppose that a binary tree has n nodes that are u_1 u_2 ... u_n in preorder and u_{p_1} u_{p_2} ... u_{p_n} in inorder. Show that the permutation p_1 p_2 ... p_n can be obtained by passing 12 ... n through a stack, in the sense of exercise 2.2.1-2. Conversely, show that any permutation p_1 p_2 ... p_n obtainable with a stack corresponds to some binary tree in this way.
Verified: no
Solve time: 37s
Solution
Let a binary tree have $n$ nodes, with preorder sequence
$$ u_1 u_2 \dots u_n $$
and inorder sequence
$$ u_{p_1} u_{p_2} \dots u_{p_n}. $$
We will show that the permutation $p_1 p_2 \dots p_n$ can be obtained by passing $1 2 \dots n$ through a stack, and conversely, that any permutation obtainable in this manner arises from a suitable binary tree.
Part 1: From a binary tree to a stack permutation
We represent the binary tree in the conventional left-right link format as in Section 2.3.1, and associate the preorder numbering $1,2,\dots,n$ with the nodes $u_1,\dots,u_n$. Let the inorder positions of these nodes be $p_1,\dots,p_n$, so that $u_i$ occupies position $p_i$ in the inorder sequence.
Consider the recursive procedure for inorder traversal using Algorithm T. Let the stack initially be empty, and let $i$ index the nodes in preorder. Each time we descend the left subtree (step T3), we push the preorder index $i$ onto the stack. When the leftmost descendant is reached, step T2 detects $P = \Lambda$, and step T4 pops the stack to obtain the next node to visit. Visiting the node corresponds to producing its inorder index $p_i$ in the output sequence. Then the right subtree is traversed recursively, repeating this process.
By induction on the number of nodes, each node is pushed exactly once onto the stack when first encountered (as we descend to its leftmost descendant), and is popped exactly once when visited. Thus, the sequence of pops from the stack produces the inorder sequence $p_1 p_2 \dots p_n$. The sequence of pushes is exactly $1 2 \dots n$ in preorder. Therefore, $p_1 p_2 \dots p_n$ is obtained from $1 2 \dots n$ by passing through a stack, in the sense of exercise 2.2.1-2.
Formally, let $T$ be the subtree rooted at node $u_i$, and let $L$ and $R$ be its left and right subtrees. By definition, the inorder sequence of $T$ is the concatenation of the inorder sequences of $L$, then $u_i$, then $R$. In Algorithm T, the nodes of $L$ are pushed and popped before $u_i$ is popped, producing exactly the correct relative order. After $u_i$ is popped, the nodes of $R$ are processed. This precisely matches the stack-permutation procedure: numbers are pushed in preorder, and the sequence of pops produces the inorder sequence $p_1 p_2 \dots p_n$. ∎
Part 2: From a stack-permutation to a binary tree
Conversely, suppose a permutation $p_1 p_2 \dots p_n$ of $1 2 \dots n$ is obtainable by passing the numbers $1 2 \dots n$ through a stack. We construct a binary tree whose preorder sequence is $1 2 \dots n$ and whose inorder sequence corresponds to $p_1 p_2 \dots p_n$.
We proceed recursively. Let $i$ be the first element of the preorder sequence (always $1$). In the stack-permutation algorithm, $i$ is pushed, and elements are popped until $i$ appears in the output. Let the numbers popped before $i$ form the left subtree; these are smaller than $i$ in the preorder sequence (since the stack is last-in-first-out). The numbers remaining to be output after $i$ form the right subtree. By the properties of stack permutations (see exercise 2.2.1-2), each subtree corresponds to a contiguous subsequence in preorder. We assign $i$ as the root, recursively construct the left and right subtrees from the corresponding subsequences, and attach them to $i$ as left and right children.
Formally, let $L$ be the sequence of elements popped before $i$ and $R$ the remaining elements in the permutation. The preorder sequence of $L$ consists of the first $|L|$ elements after $i$ in $1 2 \dots n$, and similarly for $R$. By induction on the length of $L$ and $R$, we can construct binary trees for $L$ and $R$. Attaching them as left and right subtrees of $i$ produces a binary tree whose preorder sequence is $1 2 \dots n$ and whose inorder sequence is exactly $p_1 p_2 \dots p_n$.
This construction is valid because any stack-permutation corresponds to a sequence of push and pop operations that can be simulated exactly by descending left subtrees (push) and visiting nodes (pop) in Algorithm T. ∎
Conclusion
The permutation $p_1 p_2 \dots p_n$ of the inorder sequence is obtainable from $1 2 \dots n$ via a stack. Conversely, any stack-permutation arises from the inorder sequence of some binary tree with preorder $1 2 \dots n$. Thus, there is a one-to-one correspondence between stack-permutations and binary trees labeled in preorder.
This completes the proof. ∎