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

First time here? Checkout the FAQ!

x

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