Question

In which order are the vertices of the ordered rooted tree in Exercises 8 visited using a postorder traversal?

Short answer

Therefore, the order of post-order traversal of the given ordered rooted tree is

d, i, m, n, o, j, e, b, f, g, k, p, l, h, c, a.

Step-by-step solution

General form

Post-order traversal:

Let T be an ordered root tree with root r. If Tcontains r only, then r is the post-ordertraversalof T. Otherwise, suppose that \({{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{\bf{n}}}\) are the subtrees at r from left to right. The post-order traversal begins by traversing \({{\bf{T}}_{\bf{1}}}\) in post-order, then \({{\bf{T}}_{\bf{2}}}\) in post-order, …, then \({{\bf{T}}_{\bf{n}}}\) in post-order, and ends byvisiting r.

Evaluate the given rooted tree

Referring from Exercise 8:

Given that, the ordered rooted tree.

Determine the order in which postorder traversal of the given tree.

Since, the postorder traversal, visit subtrees left to right; visit root.

Case (1):

Case (2):

Case (3):

Case (4):

So, the post-order traversal of the given ordered rooted tree is d, i, m, n, o, j, e, b, f, g, k, p, l, h, c, a.