how to build a BSt from tree traversals

[zeah]

hi
how do we build a binary search tree when post order and inorder tree traversals are given to u....and how do we make use of creat root and create tree templates in your existing code???

[manontheedge]

do you know what a binary search tree is? or how to traverse it ( in any order ) on paper?

[zeah]

do you know what a binary search tree is? or how to traverse it ( in any order ) on paper?

yes i know how all traversals work on paper..but im not able to write code for generating it from the traversals....
here is a desciption of how u build a tree from postorder and inorder traversals on papaer...

Postorder: D C B K J I A
Inorder: C D B A I J K
from post order we take the last node(A)
now A becomes the root.Search A in inorder. whereever u find A, the nodes left to A becomes the left tree(C D B) and the nodes on right forms the right tree(I J K).
Same way we take the next root from post order i.e I now then look for I in the in order.now I becomes the right node of A and J K goes to form right tree of I.
Then we go for next root i.e J and look for J in inorder...and so

so can any1 help me out with the codin of ths.....

[blah blah]

make a recursive func.. call it repeatedly. make it do what u are saying recursively...m ake two arrays to store the inorder and postorder...
then pick last ele as temp. Then temp is root node.
then search for temp index in inoder array..all ele on left will be made left tree of the temp...and right will be right.
call the func again on the left tree and the right tree and so on till u get null.........

I THINK this shud work. :/