TAOCP 2.3.1 Exercise 2

Exercise 2. [11] List the nodes of the binary tree in (a) preorder; (b) symmetric order; (c) postorder.

Exercise 2 tree.

Verified: no
Solve time: 38s

Solution

Let T denote the root of the binary tree in the figure. We denote the left and right links of a node P by LLINK(P) and RLINK(P), and the value of the node by INFO(P). Traversals are defined recursively as in Section 2.3.1.

(a) Preorder traversal. By definition, preorder visits the root first, then traverses the left subtree in preorder, and finally traverses the right subtree in preorder. Let us apply this recursively:

Visit the root A.
Traverse the left subtree rooted at B:

Visit B.
Traverse left subtree of B, rooted at D: visit D.
Right subtree of B is empty.

Traverse the right subtree rooted at C:

Visit C.
Traverse left subtree of C, rooted at E:
Visit E.
Left subtree of E is empty.
Traverse right subtree of E, rooted at G: visit G.
Traverse right subtree of C, rooted at F:
Visit F.
Left subtree of F is empty.
Traverse right subtree of F, rooted at H:
Visit H.
Left subtree of H is empty.
Traverse right subtree of H, rooted at J: visit J.

Collecting nodes in the order visited gives

$$ A \quad B \quad D \quad C \quad E \quad G \quad F \quad H \quad J. $$

(b) Symmetric (inorder) traversal. By definition, inorder visits the left subtree, then the root, then the right subtree. We proceed recursively:

Traverse left subtree of A rooted at B:

Traverse left subtree of B rooted at D: visit D.
Visit B.
Right subtree of B is empty.

Visit A.
Traverse right subtree of A rooted at C:

Traverse left subtree of C rooted at E:
Left subtree of E is empty.
Visit E.
Traverse right subtree of E rooted at G: visit G.
Visit C.
Traverse right subtree of C rooted at F:
Left subtree of F is empty.
Visit F.
Traverse right subtree of F rooted at H:
Left subtree of H is empty.
Visit H.
Traverse right subtree of H rooted at J: visit J.

Collecting nodes in order yields

$$ D \quad B \quad A \quad E \quad G \quad C \quad F \quad H \quad J. $$

(c) Postorder traversal. By definition, postorder traverses the left subtree, then the right subtree, then visits the root. We apply this recursively:

Traverse left subtree of A rooted at B:

Traverse left subtree of B rooted at D: visit D.
Right subtree of B is empty.
Visit B.

Traverse right subtree of A rooted at C:

Traverse left subtree of C rooted at E:
Left subtree of E is empty.
Traverse right subtree of E rooted at G: visit G.
Visit E.
Traverse right subtree of C rooted at F:
Left subtree of F is empty.
Traverse right subtree of F rooted at H:
Left subtree of H is empty.
Traverse right subtree of H rooted at J: visit J.
Visit H.
Visit F.
Visit C.

Visit A.

Collecting nodes in order gives

$$ D \quad B \quad G \quad E \quad J \quad H \quad F \quad C \quad A. $$

All sequences satisfy the recursive definitions of preorder, inorder, and postorder.

$$ \boxed{ \text{Preorder: } A B D C E G F H J, \quad \text{Inorder: } D B A E G C F H J, \quad \text{Postorder: } D B G E J H F C A } $$