TAOCP 2.3.1 Exercise 8
Let the nodes of a binary tree be distinct.
Section 2.3.1: Traversing Binary Trees
Exercise 8. [20] Find all binary trees whose nodes appear in exactly the same sequence in both (a) preorder and inorder; (b) preorder and postorder; (c) inorder and postorder. (As in the previous exercise, we assume that the nodes have distinct labels.)
Verified: no
Solve time: 32s
Solution
Let the nodes of a binary tree be distinct. We determine all binary trees for which the indicated traversals yield exactly the same sequence.
(a) Preorder and inorder coincide
Suppose preorder and inorder are identical.
In preorder, the root appears first. In inorder, the root appears between the left and right subtrees. Since the two sequences are the same, the root must also appear first in inorder. Therefore the left subtree of the root is empty.
Apply the same argument recursively to the right subtree. Since the preorder and inorder of the whole tree coincide, the preorder and inorder of every subtree must also coincide. Hence every node has empty left subtree.
Therefore the tree consists entirely of right links, beginning at the root:
$$ u_1 \to u_2 \to \cdots \to u_n, $$
where each node has no left child.
Conversely, any such tree has preorder
$$ u_1,u_2,\ldots,u_n, $$
since preorder visits the root and then the right subtree, and inorder
$$ u_1,u_2,\ldots,u_n, $$
since there are no left subtrees.
Hence preorder and inorder are identical if and only if every left link is null.
The complete set of such trees is therefore precisely the right-leaning chains.
$$ \boxed{\text{All binary trees in which every node has empty left subtree}} $$
(b) Preorder and postorder coincide
Suppose preorder and postorder are identical.
If the tree is nonempty, preorder begins with the root, while postorder ends with the root. Since the sequences are identical and the nodes are distinct, the first and last elements must be equal. Therefore a nonempty tree can contain only one node.
Conversely, a one-node tree has preorder and postorder both equal to the single node.
The empty tree also satisfies the condition, since both traversals are empty.
Hence the only possibilities are the empty tree and the one-node tree.
$$ \boxed{\text{Only the empty tree and the one-node tree}} $$
(c) Inorder and postorder coincide
Suppose inorder and postorder are identical.
In postorder, the root appears last. In inorder, the root appears between the left and right subtrees. Since the two sequences are the same, the root must also appear last in inorder. Therefore the right subtree of the root is empty.
Apply the same argument recursively to the left subtree. Since the inorder and postorder of the whole tree coincide, the same property must hold for every subtree. Hence every node has empty right subtree.
Therefore the tree consists entirely of left links:
$$ u_n \leftarrow u_{n-1} \leftarrow \cdots \leftarrow u_1, $$
where each node has no right child.
Conversely, any such tree has inorder
$$ u_1,u_2,\ldots,u_n, $$
because inorder traverses the left subtree before visiting the root, and postorder
$$ u_1,u_2,\ldots,u_n, $$
because postorder traverses the left subtree before visiting the root and there are no right subtrees.
Hence inorder and postorder are identical if and only if every right link is null.
$$ \boxed{\text{All binary trees in which every node has empty right subtree}} $$