Question

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

Short answer

Therefore, the order of postorder traversal of the given ordered rooted tree is

d, f, g, e, b, 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-order traversal of 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 7:

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):

So, the postorder traversal of the given ordered rooted tree is d, f, g, e, b, c, a.