TAOCP 2.3.1 Exercise 3

The statement claims that "The terminal nodes of a binary tree occur in the same relative position in preorder, inorder, and postorder.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 3. [20] Is the following statement true or false? "The terminal nodes of a binary tree occur in the same relative position in preorder, inorder, and postorder."

Verified: no
Solve time: 43s

Solution

The statement claims that "The terminal nodes of a binary tree occur in the same relative position in preorder, inorder, and postorder." Let us examine this claim rigorously.

Let a binary tree have root R and arbitrary left and right subtrees. Denote by T the set of terminal nodes, that is, nodes P for which LLINK(P) = \Lambda and RLINK(P) = \Lambda. Consider the three traversal orders:

  1. Preorder: Visit root, then traverse left subtree in preorder, then traverse right subtree in preorder.
  2. Inorder: Traverse left subtree in inorder, then visit root, then traverse right subtree in inorder.
  3. Postorder: Traverse left subtree in postorder, then traverse right subtree in postorder, then visit root.

The claim is equivalent to stating that if we list only the terminal nodes in each traversal, the sequence of these terminal nodes is identical across all three orders.

We can disprove this statement by constructing a counterexample. Consider the simplest nontrivial binary tree with root A and two children B and C, both terminal nodes:

    A
   / \
  B   C
  • Preorder traversal of all nodes: A B C. Terminal nodes are B, C.
  • Inorder traversal of all nodes: B A C. Terminal nodes are B, C.
  • Postorder traversal of all nodes: B C A. Terminal nodes are B, C.

In this simple symmetric tree, the relative order of terminal nodes B, C is indeed the same. However, consider the following asymmetric tree:

      A
     / 
    B   
     \
      C

Here B has a right child C, and C is terminal; B is not terminal; A has only a left child B.

  • Preorder traversal: Visit A, then left subtree. Left subtree preorder is B, C. Full preorder: A B C. Terminal nodes: C.
  • Inorder traversal: Traverse left subtree in inorder: traverse B's left subtree (\Lambda), visit B, traverse B's right subtree: C. Then visit root A. Full inorder: B C A. Terminal nodes: C.
  • Postorder traversal: Traverse left subtree in postorder: traverse B's left subtree (\Lambda), traverse B's right subtree: C, visit B. Then visit root A. Full postorder: C B A. Terminal nodes: C.

Here the terminal node C occurs in the same singleton sequence, so relative order is trivially the same. To find a genuine counterexample, consider a tree with multiple terminal nodes in different subtrees of different heights:

      A
     / \
    B   D
   /     \
  C       E

Terminal nodes are C and E. Compute traversals:

  • Preorder: A B C D E. Terminal nodes: C, E.
  • Inorder: Left subtree inorder: C B. Right subtree inorder: D E. Full inorder: C B A D E. Terminal nodes: C, E.
  • Postorder: Left subtree postorder: C B. Right subtree postorder: E D. Full postorder: C B E D A. Terminal nodes: C, E.

Again the relative order of terminal nodes is C, E in all three traversals. To break the pattern, consider a deeper nested asymmetric tree:

       A
      / \
     B   D
    / \
   C   E
        \
         F

Terminal nodes are C, F, D. Compute traversals:

  • Preorder: A B C E F D. Terminal nodes: C, F, D.
  • Inorder: Left subtree inorder: C B E F. Right subtree inorder: D. Full inorder: C B E F A D. Terminal nodes: C, F, D.
  • Postorder: Left subtree postorder: C F E B. Right subtree postorder: D. Full postorder: C F E B D A. Terminal nodes: C, F, D.

Still relative order is C, F, D. This indicates that terminal nodes do appear in the same relative order, provided "relative position" is interpreted as their left-to-right appearance in the tree structure. That is, terminal nodes are visited in left-to-right order in all three traversals, because each traversal respects the left-right hierarchy of the tree. Preorder and postorder do not visit the root before or after every subtree in a way that changes the left-right sequence of leaves. Inorder preserves left-to-right order by definition.

Formally, for any two terminal nodes P and Q, if P is in the left subtree of the least common ancestor of P and Q and Q is in the right subtree, then P precedes Q in every traversal. If both are in the same subtree, induction on that subtree ensures the relative order is preserved. By induction on the size of the tree, this property holds for all terminal nodes.

Hence the statement is true.

This completes the proof.

∎

Notes

The key observation is that traversal order does not affect the left-to-right sequence of terminal nodes, even though the positions of nonterminal nodes differ in preorder, inorder, and postorder.