Prev: Trying to obtain free version of On Misere Games by Ranan Banerji and Charles Dunning
Next: A little to the right >>>>>>>>>>>>>>>>>>>>
From: Merciadri Luca on 27 Apr 2010 13:13
Hi,

As stated in the title, I would like to know if, being given three
sequences (the preorder, the inorder and the postorder), there is only
one binary tree respecting these sequences. If so, it is unique.

And, furthermore, does such a tree always exist?

Thanks folks.
From: Mike Terry on 27 Apr 2010 13:57
"Merciadri Luca" <merciadriluca(a)gmail.com> wrote in message
news:d27fcb88-8f2b-4582-89fd-80dbc68db6f6(a)r1g2000yqb.googlegroups.com...
> Hi,
>
> As stated in the title, I would like to know if, being given three
> sequences (the preorder, the inorder and the postorder), there is only
> one binary tree respecting these sequences. If so, it is unique.
>
> And, furthermore, does such a tree always exist?
>
> Thanks folks.

Given the three sequences, there is at most one binary tree respecting the
sequences.

If there is a tree respecting these orderings, then looking at the preorder
sequence, we must find successively:
- the root node
- a set of nodes that precede the root node in the inorder sequence
- a set of nodes that follow the root node in the inorder sequence
(if we don't find this, there is no tree respecting the orders - it is easy
to construct an example where this happens)

So we can identify the root node, and the nodes on its left and right
branches. Proceeding recursively we can reconstruct the whole tree. (Or
find in the process that there is no such tree.)

Finally, having reconstructed the tree, we can check whether or not the
postorder is also respected. (Note there is at most one tree which
satisfies the pre- and in-orders, before we even start to talk of
postorders...)

Regards,
Mike.



From: Mike Terry on 27 Apr 2010 14:29
"Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message
news:kpednS9wLJQSuErWnZ2dnUVZ8qudnZ2d(a)brightview.co.uk...
> "Merciadri Luca" <merciadriluca(a)gmail.com> wrote in message
> news:d27fcb88-8f2b-4582-89fd-80dbc68db6f6(a)r1g2000yqb.googlegroups.com...
> > Hi,
> >
> > As stated in the title, I would like to know if, being given three
> > sequences (the preorder, the inorder and the postorder), there is only
> > one binary tree respecting these sequences. If so, it is unique.
> >
> > And, furthermore, does such a tree always exist?
> >
> > Thanks folks.
>
> Given the three sequences, there is at most one binary tree respecting the
> sequences.
>
> If there is a tree respecting these orderings, then looking at the
preorder
> sequence, we must find successively:
> - the root node
> - a set of nodes that precede the root node in the inorder sequence
> - a set of nodes that follow the root node in the inorder sequence
> (if we don't find this, there is no tree respecting the orders - it is
easy
> to construct an example where this happens)

Hmmm, one or both of the above sets of course could be empty - that just
means that there are no left/right nodes below the root in the tree, which
is OK. What we can't have is a node on the right side of the tree appearing
before a node on the left in the preorder sequence...

>
> So we can identify the root node, and the nodes on its left and right
> branches. Proceeding recursively we can reconstruct the whole tree. (Or
> find in the process that there is no such tree.)
>
> Finally, having reconstructed the tree, we can check whether or not the
> postorder is also respected. (Note there is at most one tree which
> satisfies the pre- and in-orders, before we even start to talk of
> postorders...)
>
> Regards,
> Mike.
>
>
>


From: Merciadri Luca on 27 Apr 2010 14:46
On Apr 27, 7:57 pm, "Mike Terry"
<news.dead.person.sto...(a)darjeeling.plus.com> wrote:
> "Merciadri Luca" <merciadril...(a)gmail.com> wrote in message
>
> news:d27fcb88-8f2b-4582-89fd-80dbc68db6f6(a)r1g2000yqb.googlegroups.com...
>
> > Hi,
>
> > As stated in the title, I would like to know if, being given three
> > sequences (the preorder, the inorder and the postorder), there is only
> > one binary tree respecting these sequences. If so, it is unique.
>
> > And, furthermore, does such a tree always exist?
>
> > Thanks folks.
>
> Given the three sequences, there is at most one binary tree respecting the
> sequences.
>
> If there is a tree respecting these orderings, then looking at the preorder
> sequence, we must find successively:
> - the root node
> - a set of nodes that precede the root node in the inorder sequence
> - a set of nodes that follow the root node in the inorder sequence
> (if we don't find this, there is no tree respecting the orders - it is easy
> to construct an example where this happens)
>
> So we can identify the root node, and the nodes on its left and right
> branches.  Proceeding recursively we can reconstruct the whole tree.  (Or
> find in the process that there is no such tree.)
>
> Finally, having reconstructed the tree, we can check whether or not the
> postorder is also respected.  (Note there is at most one tree which
> satisfies the pre- and in-orders, before we even start to talk of
> postorders...)

Thanks for your answer. Very useful.
From: Merciadri Luca on 27 Apr 2010 14:48
On Apr 27, 8:29 pm, "Mike Terry"
<news.dead.person.sto...(a)darjeeling.plus.com> wrote:
> Hmmm, one or both of the above sets of course could be empty - that just
> means that there are no left/right nodes below the root in the tree, which
> is OK.  What we can't have is a node on the right side of the tree appearing
> before a node on the left in the preorder sequence...
>
>
>
> > So we can identify the root node, and the nodes on its left and right
> > branches.  Proceeding recursively we can reconstruct the whole tree.  (Or
> > find in the process that there is no such tree.)
>
> > Finally, having reconstructed the tree, we can check whether or not the
> > postorder is also respected.  (Note there is at most one tree which
> > satisfies the pre- and in-orders, before we even start to talk of
> > postorders...)
Thanks for this modification.
 | 
Pages: 1
Prev: Trying to obtain free version of On Misere Games by Ranan Banerji and Charles Dunning
Next: A little to the right >>>>>>>>>>>>>>>>>>>>