91Ó°ÊÓ

Let's consider the two trees given in Figure 22-3: Tree 1: ``` A / \ B C /|\ D E F ``` Tree 2: ``` X /|\ Y Z W ```

To perform postorder traversal on Tree 1, follow the L-R-R (left-right-root) order: 1. Traverse the left subtree of A, which is B. 2. Traverse the left subtree of B, which is D. As D is a leaf node, it becomes the first element in the output. 3. Traverse the right subtree of B. It has two children: E and F. 4. Traverse the left subtree of E, which has no children. 5. Traverse the right subtree of E, which has no children. 6. Add E to the output. 7. Traverse the left subtree of F, which has no children. 8. Traverse the right subtree of F, which has no children. 9. Add F to the output. 10. Since we have traversed both of B's children, add B to the output. 11. Traverse the right subtree of A, which is C. 12. Traverse the left subtree of C, which has no children. 13. Traverse the right subtree of C, which has no children. 14. Add C to the output. 15. Finally, add A to the output, as both its children have been traversed. The postorder traversal of Tree 1 is: D, E, F, B, C, A

To perform postorder traversal on Tree 2, follow the L-R-R (left-right-root) order: 1. Traverse the left subtree of X, which is Y. 2. Traverse the left subtree of Y, which has no children. 3. Traverse the right subtree of Y, which has no children. 4. Add Y to the output. 5. Traverse the right subtree of X, which is W. 6. Traverse the left subtree of W, which has no children. 7. Traverse the right subtree of W, which has no children. 8. Add W to the output. 9. Traverse the middle subtree of X, which is Z. 10. Traverse the left subtree of Z, which has no children. 11. Traverse the right subtree of Z, which has no children. 12. Add Z to the output. 13. Finally, add X to the output, as all its children have been traversed. The postorder traversal of Tree 2 is: Y, W, Z, X Conclusion: The postorder traversal of Tree 1 is D, E, F, B, C, A, and the postorder traversal of Tree 2 is Y, W, Z, X.