=========================preview======================
(COMP171)The solution for Question 1.pdf
Back to COMP171 Login to download
======================================================
The solution for Question 1(C) (Spring 05 Midterm Exam) is as shown below.

The trick in solving this problem is to notice that B is the last element in the postorder sequence. Thus, B must be a root node.

However, B is also the first in the in order traversal C thus, the tree must have an empty left subtree.

Then, since G is the second last element, thus G must be the root of the right subtree, and {C, D, E} belong to the left substree rooted at G, and H is the root of the right subtree rooted at G. The rest of the argument can follow similarly.