Question

tree with root vertex d that has a left edge to f, a center edge to b, and a right edge to a. b has a left edge to i, a center edge to h, and a right edge to e. a has a center edge to c. c has a center edge to g. (a) give the order in which the vertices of the tree are visited in a post-order traversal. (b) give the order in which the vertices of the tree are visited in a pre-order traversal.

Answer 1

• post-order: f, i, h, e, b, g, c, a, d
• pre-order: d, f, b, i, h, e, a, c, g

Explanation:

You want the (a) post-order, and (b) pre-order list of visited vertices in a traversal of the tree described by {root, left, center, right}: {d, f, {b, i, h, e}, {a, {c, g}}}.

(a) Post-order

A tree is traversed in post-order by visiting the left branch, center branch, and right branch before the root. This is accomplished recursively.

For the given tree, the root 'd' has left branch 'f' which has no branches. That means node 'f' is reported first.

The middle branch goes to 'b' which has three branches. Those are reported before their root 'b'.

The right branch from root 'd' goes to 'a', which has branch 'c' going to 'g'. So, 'g' is reported, then 'c', then 'a'.

Finally, 'd' is reported.

Hence, the post-order traversal is f, i, h, e, b, g, c, a, d.

(b) Pre-order

The pre-order traversal reports the root node, then the left, center, and right nodes, recursively. The vertices are effectively visited in the order in which we have defined the tree above: d, f, b, i, h, e, a, c, g.