Question

Construct the binary tree for Postorder and Inorder given sequence

Postorder : D E F B G L J K H C A
Inorder : D B F E A G C L J H K

Answer 1

Construction of Tree:

Step1: Select last element from the postorder as root node. So element A
becomes root node. Divide the inorder into left and right with respect to
root node A.

Step 2: Traverse element D B F E from postorder as B comes in last B
becomes child node of A and similarly traverse G C L J H K in postorder
C comes at last C becomes child node of A. Again with respect to B and
C divide element into left and right as shown below

Step 3: As D is single it becomes child node of B and for left node of B
Traverse F E in postorder F comes at last so F becomes child node of B.
similarly, G and H become child node of C as shown below.

Step 4: As E is single it becomes child node of F. Traverse L J which is
left element of node H in postorder as J comes last J becomes child node
of H as K is single it becomes another child node.

Step 5: As L is single it becomes child node of J