Question

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

Short answer

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

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

Step-by-step solution

General form

Post-order traversal:

LetT be an ordered root tree with root r. If Tcontains only of r, then r is the post-order traversalof 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 by visiting r.

Evaluate the given rooted tree

Referring from Exercise 9:

Given that, the ordered rooted tree.

Determine the order in which post-order traversal of the given tree.

Since, the post-order 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 k, l, m, e, f, r, s, n, g, b, c, o, h, i, p, q, j, d, a.