CHAP. 10] BINARY TREES 241
EXAMPLE 10.3 Consider the binary treeTin Fig. 10-7(a). Observe thatAis the root ofT, that the left subtree
LTofTconsists of nodesB,D, andE, and the right subtreeRTofTconsists of nodesCandF.
(a) The preorder traversal ofTprocessesA, traversesLT, and traversesRT. However, the preorder traversal of
LTprocesses the rootB, and thenDandE; and the preorder traversal ofRTprocesses the rootCand then
F. ThusABDECFis the preorder traversal ofT.(b) The inorder traversal ofTtraversesLTprocessesA, and traversesRT. However, the inorder traversal ofLT
processesD,B, and thenE; and the inorder traversal ofRTprocessesCand thenF. ThusDBEACFis the
inorder traversal ofT.
(c) The postorder traversal ofTtraversesLT, traversesRT, and processesA. However, the postorder traversal
ofLT, processesD,E, and thenB, and the postorder traversal ofRTprocessesFand thenC. Accordingly,
DEBFCAis the postorder traversal ofT.Fig. 10-7EXAMPLE 10.4 LetTbe the binary tree in Fig. 10-7(b). The preorder traversal is as follows:
(Preorder)ABDEF CGH J LKThis order is the same as the one obtained by scanning the tree from the left as indicated by the path in
Fig. 10-7(b). That is, one “travels” down the leftmost branch until meeting a terminal node, then one back-
tracks to the next branch, and so on. In the preorder traversal, the rightmost terminal node, nodeK, is the last node
scanned. Observe that the left subtree of the rootAis traversed before the right subtree, and both are traversed
afterA. The same is true for any other node having subtrees, which is the underlying property of a preorder
traversal.
The reader can verify by inspection that the other two ways of traversing the treeTin Fig. 10-7(b) are as
follows:
(Inorder) DBF EAGCLJ H K
(Postorder)DF EBGLJ KH CA
Remark: Observe that the terminal nodes,D,F,G,L, andK, of the binary tree in Fig. 10-7(b) are traversed in
the same order, from left to right, in all three traversals. We emphasize that this is true for any binary treeT.