Question

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

Short answer

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

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

Step-by-step solution

General form

In-order traversal:

Let T be an ordered root tree with root r. If T contains r only, then r is thein-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 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 9:

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

Case (4):

So, the inorder traversal of the given ordered rooted tree is k, e, l, m, b, f, r, n, s, g, a, c, o, h, d, i, p, j, q.