Question

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

Short answer

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

d, b, f, e, g, a, c.

Step-by-step solution

General form

In-order traversal:

Let T be an ordered rooted tree with root r. If Tconsists only of r, then r is thein-order traversalof T. Otherwise, suppose that \({{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{\bf{n}}}\) arethe subtrees at r from left to right. The in-order traversal begins by traversing \({{\bf{T}}_{\bf{1}}}\) in in-order, then visiting r. It continues by traversing \({{\bf{T}}_{\bf{2}}}\) in in-order, and so on, until \({{\bf{T}}_{\bf{n}}}\) is traversed in in-order.

Evaluate the given rooted tree

Referring from Exercise 7:

Given that, the ordered rooted tree.

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

Since, the inorder traversal, visit leftmost subtree, visit root, visit other subtrees left to right.

Case (1):

Case (2):

Case (3):

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