Constructing Binary tree

> Sure, but it doesn't mention anywhere how a tree can

> be constructed

> from two of the three pre/in/post-order traversals

> ...

>

> kind regards,

>

> Jos

Woops, thought the OP was a lazy student! (I didn't read the post with a lot of attention).

@OP: Sorry!

prometheuzza at 2007-7-15 18:18:41 >

> Jos it's very kind of you,but i have one doubt..

> How to find the number of nodes per level?

As I wrote (see above): update an ArrayList a where a[ i ] == n implies

that level i contains n nodes. Something like this:public void findDiameter(Node node, int level) {

if (node == null) return;

incrementLevelAt(level);

findDiameter(node.getLeft());

findDiameter(node.getRight());

}

kind regards,

Jos

JosAHa at 2007-7-15 18:18:41 >

> Let p_1, p_2 ... p_n be the postorder traversal and

> let i_1, i_2 ... i_n

> be the inorder traversal. From the postorder

> traversal we know that

> the root of the tree is p_n. Find this element in the

> inorder traversal,

> say i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n. From the

> inorder traversal we

> find all the elements in the left subtree, i.e. i_1,

> i_2 ... i_k-1 and in

> the right subtree, i.e. i_k+1 ... i_n respectively.

>

> Remove element p_n (and element i_k == p_n). Find the

> rightmost

> element p_j in p_1, p_2 ... p_j ... p_n-1 where p_j

> is an element in

> i_1, i_2 ... i_k-1. This is the root of the left

> subtree of the original tree.

>

> Split p_1, p_2 ... p_j and p_j+1 ... p_n-1 and i_1,

> i_2 ... i_k-1 and

> i_k+1 ... i_n. Now you have two subsequences

> representing the

> postorder and inorder traversal of the two subtrees

> of the original

> tree.

chanced upon this forum.

i would just like to ask if i can do that algorithm on the two arrays or i need to "split" it into two ("left son" and "right son") arrays.

arviNatora at 2007-7-15 18:18:41 >

Assuming there are no repeated labels, how can one construct the binary tree? I'm stumped with the first given algorithm.

Given:

Postorder: LEYPCZHSGTA

Inorder: LEZYCPATHGS

what am i supposed to do after

LEYPCZHSGT

LEZYCP*THGS

that's the part after i've removed the root and has separated the two sequences...

arviNatora at 2007-7-15 18:18:41 >

> help...

The following output I got from an implementation of Jos' recursive algoritm.

Ok, here we go:

===================================================

postorder = [L, E, Y, P, C, Z, H, S, G, T, (A)]

inorder= [L, E, Z, Y, C, P, (A), T, H, G, S]

root = 'A', level = 0

We find that 'A' is the root. Mark this one also

in the inorder traversal. Now look for the first

occerrence in the postorder traversal (from right

to left!) which is also in [L, E, Z, Y, C, P].

This is 'Z', and will get the following:

===================================================

postorder = [L, E, Y, P, C, (Z)]

inorder= [L, E, (Z), Y, C, P]

left root = 'Z', level = 1

So 'Z' is the left root. Look again for the first

occurrence of a character in the postorder (right

to left) which is in [L, E]. So we get:

===================================================

postorder = [L, (E)]

inorder= [L, (E)]

left root = 'E', level = 2

===================================================

postorder = [(L)]

inorder= [(L)]

left root = 'L', level = 3

===================================================

postorder = [Y, P, (C)]

inorder= [Y, (C), P]

right root = 'C', level = 2

===================================================

postorder = [(Y)]

inorder= [(Y)]

left root = 'Y', level = 3

===================================================

postorder = [(P)]

inorder= [(P)]

right root = 'P', level = 3

===================================================

postorder = [H, S, G, (T)]

inorder= [(T), H, G, S]

right root = 'T', level = 1

===================================================

postorder = [H, S, (G)]

inorder= [H, (G), S]

right root = 'G', level = 2

===================================================

postorder = [(H)]

inorder= [(H)]

left root = 'H', level = 3

===================================================

postorder = [(S)]

inorder= [(S)]

right root = 'S', level = 3

===================================================

finally done!

; )

This represents the following tree:

level

A0

/ \

/\

ZT 1

/ \\

ECG2

// \/ \

LYP HS3

Hope this helps a bit.

prometheuzza at 2007-7-20 14:37:33 >

> if this may sound easy, i really really really need

> your help...

This is the method I used:

private void constructTree(List<Character> postOrder, List<Character> inOrder, int level) {

level++;

Character root = /* the last element from the postOrder (use List.remove(...)) */;

List<Character> leftSubtree = /* this is: inOrder[0, ..., indexOf(root)] */;

Character leftRoot = null;

for(int i = postOrder.size()-1; i >= 0; i--) {

/*

the 'leftRoot' is defined as the first character

which is in 'leftSubtree' and in 'postOrder'

*/

}

System.out.println( /* print the root and the level */ );

List<Character> newPostOrderA, newInOrderA, newPostOrderB, newInOrderB;

newPostOrderA = /* is: postOrder[0, ..., postOrder.indexOf(leftRoot)+1] */;

newInOrderA= /* is: inOrder[0, ..., inOrder.indexOf(root)] */;

if(/* there are elements in 'newPostOrderA' */) {

System.out.print("left ");

/* make a recursive call with these new left in- and postorder traversals */

}

newPostOrderB = /* is: postOrder[postOrder.indexOf(leftRoot)+1, ..., postOrder.size()] */;

newInOrderB= /* is: inOrder[inOrder.indexOf(root)+1, ..., inOrder.size()] */;

if(/* there are elements in 'newPostOrderB' */) {

System.out.print("right ");

/* make a recursive call with these new right in- and postorder traversals */

}

}

I've commented some things out. It's for you to finish it.

Good luck.

prometheuzza at 2007-7-20 14:37:33 >

Ater you split the in-order tree, you know know the size of the two sub trees so you can split the reaminder of the post-order into its two subtrees since they must match the sizes. This gives you an in and post pair for the left subtree of the root and also an in and post pair for the right subtree.

Given:

Postorder: LEYPCZHSGTA

Inorder: LEZYCPATHGS

1)find last elt of post order in the in order,

2)count the sizes of the two subtrees from the in order and split the post order by that same count

(LEYPCZHSGTA-LEZYCPATHGS)

1: (LEYPCZHSGT[A]-LEZYCP[A]THGS)

2: (A(LEYPCZ-LEZYCP)(HSGT-THGS))

recurse

1: (A(LEYPC[Z]-LE[Z]YCP)(HSG[T]-[T]HGS))

2: (A(Z(LE-LE)(YPC-YCP))(T()(HSG-HGS)))

recurse

1: (A(Z(L[E]-L[E])(YP[C]-Y[C]P))(T()(HS[G]-H[G]S)))

2: (A(Z(E(L-L)())(C(Y-Y)(P-P))(T()(G(H-H)(S-S))))

eventually you get

(A(Z(E(L()())())(C(Y()())(P()()))(T()(G(H()())(S()()))))

/*

A

ZT

ECG

LY PH S

*/

marlin314a at 2007-7-20 14:37:33 >

it's been a long time since i last visited here. hmmm...

i guess i'll try it in recursive next time. i have a new problem, which is finding the longest path given a graph.

btw, since i really had a hard time understanding the recursive approach... i used an iterative way. Also, our prof required us to use pointers. so, i was forced to used turbo c.

i'll study the algo that you gave... thanks!!! thank you so much!!!!

arviNatora at 2007-7-20 14:37:33 >

> Please start a new thread for this question. The

> subject Constructing Binary tree would be a

> bit off for this.

> When you make a new thread, please show that you've

> given it a thought yourself. Write the

> code/pseudo-code of the things you've tried. Explain

> what it is that's giving you trouble.

I found an existing forum about my question. I was not exactly asking for any help regarding my new problem in this forum. but, thanks for the tip as regards making new threads!

thanks again!!

arviNatora at 2007-7-20 14:37:33 >