Form a binary tree from the given order?

[Saddam Khalil]

In-order : d h b i e a f c g j 

Post-order : h d i e b f j g c a

Is it necessary the tree we form should  be same  as  the tree from where we get these orders?  

[Mehreen Saeed]

Saddam

Given these two orders, you can probably only form one unique binary tree.  Try it out.  If 'a' is at the end in post order it means 'a' is the root.

Now look at inorder: d h b i e a f c g j :  This means dhbje are at left of root (a) and fcgj are at the right of a

Keep going like this to construct the binary tree.  Your resultant tree should satisfy the two given traversals.

Mehreen

--
You received this message because you are subscribed to the Google Groups "DSFAST2015" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dsfast2015+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/dsfast2015/656aaea3-c97b-4e0c-9074-c24dc645282e%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Saddam Khalil]

Mam, how to select node from fcgj ?

    and how to select left, right and node from dh?

[Mehreen Saeed]

I give you a hint only.  Post order always prints the root of a subtree/tree in the end.  So if we have a set of nodes, from their postorder we can decide their root as it is the last one visited.  Does this help??? Post us the solution.

Mehreen

To view this discussion on the web visit https://groups.google.com/d/msgid/dsfast2015/d437fad5-5dfd-4c42-a532-e0c7090f36b1%40googlegroups.com.

[Saddam Khalil]

sorry Mam for not mentioning that i was forming tree from inorder   d h b i e a f c g j 

i found parent(dhbie) of 'dh'   and 'ie'   i.e b. But how  to find the parent from dh and ie. and how to place(direction) the chlids from dh and  ie . 

how to find parent from (fcgj)?

[Mehreen Saeed]

In-order : d h b i e a f c g j 

Post-order : h d i e b f j g c a

Look at only fcgj and look at its traversal for only fcgj

post order: fjgc

inorder: fcgj

this means c is the root (from postorder)

now from inorder f is left and gj is right

Keep repeating in the same way for gj

Does this clear the confusion???  Please post the final solution.

Mehreen

On Sat, Jun 6, 2015 at 9:16 PM, Hassan Mirza <hassanm...@gmail.com> wrote:

mam, if we do this in in-order, what will be node and what will be the child node in  this given tree??

please  clear this ambiguity..

To view this discussion on the web visit https://groups.google.com/d/msgid/dsfast2015/CAH0-8fxybk%2B%3DL%3DCd%3DfJvHv8AYCYAsXxZ5XMt_c4CrXDmicgFOw%40mail.gmail.com.

[Saddam Khalil]

Solution from In-order : d h b i e a f c g j

[Saddam Khalil]

both give the same result when we form inorders 

On Saturday, June 6, 2015 at 5:37:54 PM UTC+5, Saddam Khalil wrote:

[Mehreen Saeed]

Saddam, the placement of i is not correct. Your tree doesnot satisfy inorder. Zain's solution is correct. The final tree should satisfy both inorder and postorder. 

Mehreen

-------- Original message --------
From Saddam Khalil <saddam...@gmail.com>
Date: 06/06/2015 23:53 (GMT+05:00)
To dsfas...@googlegroups.com
Subject Re: Form a binary tree from the given order?

--

You received this message because you are subscribed to the Google Groups "DSFAST2015" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dsfast2015+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/dsfast2015/9778ce6c-4683-4bbf-a25f-327a57e1c2d2%40googlegroups.com.