Let T be the general tree in Fig. 7.94(a). (a) Traverse T in preorder. (b) Traverse T
in postorder.
Note that T has the root A and subtrees T
1
, T
2
and T
3
such that: T
1
consists of
nodes B, C, D and E.
T
2
consists of nodes F, G and H.
T
3
consists of nodes J, K, L, M, N, P and Q.
(a) The preorder traversal of T consists of the following steps:
(i)Process root A.
(ii)Traverse T
1
in preorder: Process nodes B, C, D, E.
(iii)Traverse T
2
in preorder: Process nodes F, G, H.
(iv)Traverse T
3
in preorder: Process nodes J, K, L, M, P, Q, N.
That is, the preorder traversal of T is as follows:
A, B, C, D, E, F, G, H, J, K, L, M, P , Q, N
(b) The postorder traversal of T consists of the following steps:
(i)Traverse T
1
in postorder: Process nodes C, D, E, B.
(ii)Traverse T
2
in postorder: Process nodes G, H, F.
(iii)Traverse T
3
in postorder: Process nodes K, L, P, Q, M, N, J.
(iv)Process root A.
In other words, the postorder traversal of T is as follows:
C, D, E, B, G, H, F, K, L, P , Q, M, N, J, A
7.24 Consider the binary tree T ′ in Fig. 7.94(b). Find the preorder, inorder and
postorder traversals of T ′. Compare them with the preorder and postorder
traversals obtained in Solved Problem 7.23 of the general tree T in Fig.
7.94(a).
Using the binary tree traversal algorithms in Sec. 7.4, we obtain the following
traversals of T ′: Preorder: A, B, C, D, E, F, G, H, J, K, L, M, P, Q, N
Inorder: C, D, E, B, G, H, F, K, L, P, Q, M, N, J, A
Postorder: E, D, C, H, G, Q, P, N, M, L, K, J, F, B, A
Observe that the preorder of the binary tree T ′ is identical to the preorder of the
general T, and that the inorder traversal of the binary tree T ′ is identical to the
postorder traversal of the general tree T. There is no natural traversal of the