Constructing a binary tree from its traversals

[Keshan Pillay]

Firstly, thanks to everyone for answering my previous topics, my assignment is going really well. I'm now on part 2, and I need to construct a binary tree from its post-order and in-order traversals. The sample traversals given were:

Inorder traversal: ADHGKLMRUVTW
Postorder traversal: AHDLKGUVRWTM

Can someone please help me with the algorithm to complete this process?

Many thanks,
Yoonsi

[Satya Maheshwari]

I will give you a clue from which you can deduce the algorithm easily

[B]Inorder traversal: ADHGKLMRUVTW
Postorder traversal: AHDLKGUVRWTM
 
Notation: (Left Subtree) root (Right Subtree)
 
Postorder traversal: AHDLKGUVRWTM
<-------Traverse this way--------
 
Work on Inorder traversal while travesring Postorder traversal
 
(ADHGKL) M (RUVTW)
(ADHGKL) M ((RUV) T (W))
(ADHGKL) M ((R(UV)) T (W))
(ADHGKL) M ((R((U)V)) T (W))
((ADH)G(KL)) M ((R((U)V)) T (W))
((ADH)G(K(L))) M ((R((U)V)) T (W))
(((A)D(H))G(K(L))) M ((R((U)V)) T (W))[/B]

[Keshan Pillay]

Hey thanks for the reply. I can't say that your "clue" helped me very much, I already had the tree, but I should have mentioned that. But I managed to get it in the end, so thanks anyway!

[Campbell Ritchie]

Well done How did you do it? Other people can learn from your example.