Reconstructing a binary tree from RTAGs and LTAGS

[13lade619]

Not necessarily a code related question, more on the algorithm.

How do you reconstruct a binary tree with the given?

0 denotes that it doesnt have a son
1 denotes that it has a son.

Postorder

NODE ABCDEFGHIJKL
LTAG 010010110010
RTAG 000010111011

from that it means that the root node (since it's in postorder) is L has no left son but has a right son

 

[phyrex1an]

What would the correct tree be for that input?
Here is one possible (I hope...) algo:

Input: [(ltag, rtag)]

for each e in input
    n = new node
    if e.ltag then n.left = pop_stack
    if e.rtag then n.right = pop_stack
    push_stack n
end
return pop_stack

You could change the stack to a queue and get another tree.

 

[13lade619]

on the first post, I dont know the correct answer yet ^^

but here's an example in preorder.

a
/\
b c
  /\
 d  e

in PreOrder...

NODE a b c d e
LTAG 1 0 1 0 0
RTAG 1 0 1 0 0

yeah, we did this in class but i cant seem to remember...

 

[saw792]

---L-----------
----\----------
-----K---------
----/--\--------
---J----I-------
---------\------
----------H-----
---------/--\----
--------G----F---
-------/--\------
------E----D-----
-----/--\---------
----C----B-------
--------/---------
-------A----------

That looks like the correct solution. I started from the root node. Not sure if that will help you with the algorithm or not.