Constructing Binary Tree From Traversal

[bennyscuba]

I know this question has been addressed in other places but I have a slight twist on it. I want re-construct a binary tree, given the pre-order and inorder traversals. The link below shows good psuedo-code for this problem:

constructing a binary tree from its inorder and preorder traversals - C and C++ - Forums at ProgrammersHeaven.com

and this link shows the algorithm explicitly:
AcmeArticles : Reconstruction of binary trees from traversals

My problem is that these algorithms assume (I think) that all the node values are unique which is not the case in my data. I have duplicate node values. I was wondering if it is still possible to re-construct the tree?

If not, in my data I do know which nodes are terminal nodes (they all have the data value: -99). In this case I assume I should be able to reconstruct the tree with just pre-order - I know I can do it by hand.

I'm not a programmer (I'm a statistician who uses C), so I'm getting a bit lost in all of the recursion. I was wondering if anyone could assist.

Thank you,

Ben

[tabstop]

If you can do it by hand, then you're done. Write down what you do, carefully and completely, and that's your program.

[bennyscuba]

the problem is that i'm getting lost in the recursion - i'm very much a self taught programmer! what I have is (but doesn't work properly) is:
insert

node* reconstruct(int *tvar, int *tlev,  int *pi, int Len){
  node *pnode;
  pnode = nmalloc(); //malloc a node 
  
   if(*pi > Len)return NULL;

  pnode->var_split = tvar[0];
  pnode->lev_split = tlev[0];

  
  if(tvar[0] == -99){
    return pnode;
  }
  *pi += 1;
  
  pnode->left = reconstruct(tvar+1, tlev+1, pi, Len);
  pnode->right = reconstruct(tvar+1, tlev+1, pi, Len);
  return pnode;
  
}

[quzah]

Unless 'tvar' and 'tlev' are arrays, you're not doing it right. You also don't check to see if pnode fails or not.


Quzah.

[bennyscuba]

yes tvar & tlev are both arrays - that are elements of the node (the node has two data elements)

what do you mean checking to see if pnode fails?

thanks,

bg

[quzah]

What happens if malloc returns NULL?

Anyway, it looks like you're passing the same array location to both left and right trees. Won't that just end up making your tree be:

array { 1, 2, 3, 4 }
...

      tree
        1
    2      2
  3  3   3   3

That doesn't sound like it's what you want.


Quzah.

[bennyscuba]

A) that is what nmalloc does - it mallocs a node but also checks...

B) Yes that is kind of what happens - like i said i know this doesn't work but i'm entirely sure on the fix - I admit my intuition around recursion isn't that great...

Thanks for replies...

bg

[bennyscuba]

So I think I have made a bit of progress on this. I got the idea laid out that every time I see a terminal node (-99) the next node has to go to the right. So I thought this code should work. The problem is that it just makes one long list (going left and right) instead of unwinding and recursing up. any thoughts:
insert

node* reconstruct4(int *tvar, int *pi, int len) {
  node *pnode;
  pnode = nmalloc();

  pnode->var_split = tvar[*pi];

  if(*pi >= len)return NULL;

  if(tvar[*pi] != -99){
    *pi += 1;
    pnode->left = reconstruct4(tvar, pi, len);
  }
    *pi += 1;
    pnode->right = reconstruct4(tvar, pi, len);

  return pnode;

}

[quzah]

Ok, let's say this is your file has a couple of ways of being:

1
2
3
-99
-99
-99
-99

Now does your file look something like that? Or maybe:

-99
3
-99
1
-99
2
-99

How is your file built? That should help you figure out how it's to be processed.


Quzah.

[bennyscuba]

Quzah,

The file is output in preoder. so the first list would represent just a long strand while the second list would not be possible (-99 can't be a root)...That's why I say that after every -99 (a terminal node) that next node has to go to the right. I think the code above should be correct but i'm not sure why it's not recursing properly...

I really appreciate this...

Ben

[tabstop]

Do you intend *pi += 1 to change the value of pi?

[bennyscuba]

yes - that is a pointer to where i am along my list of vars. is that not correct?

bg

[tabstop]

So if you want to change the value of pi, change the value of pi:

pi += 1;

[bennyscuba]

I don't think that would work - in my program i enter pi a pointer declare so i need to change what it's pointing to (not the pointer itself) - is that correct? this is my limited understanding of pointers.

bg

[quzah]

So basically:

foo(x,y)
{
    if read from x didn't fail (not at file end)
        put y ? right : left
        if what we read was -99
            return
        foo( x, right )
        foo( x left )
    return
}

Something like that I think. You'll have to tweak it to add safety to your read checking.


Quzah.