I recently had an assignment for an advanced coding class where I was to create a Binary tree from inorder and preorder traversals. I first started out by creating my ADT for binary trees and working with that to create a new tree. The way I worked it was that I started by storing inorder traversal in an array and preorder in a queue and then I went through dividing the array into smaller arrays and passing it to the function again, recursively. The base case was when there was only one element in the array, i.e. a leaf. and this was returned by the function.

The problem I encountered was that my tree had a destructor and was being destroyed before the function could send it back since it was declared as a local variable for the setupFunction. I tried everything from pointers to references but everytime the subtree was corrupted.

I did end up converting the recursion into a while loop. But my question is, if you are trying the return a custom ADT from a recursive call, how should you do it?

Passing by reference/pointer should work, are you sure your are passing by reference, not creating a local copy?

if you post some code, then it will be much more helpful to figure out why recursion is not working with reference.

I think the problem might be the local copy thing. I'll post some code after Thursday, thats when the assignment is due and I seriously don't want to breach the Academic policy ;)

Your poll does not allow me to select more than one alternative. I would like to select #3 and #4 but I can't.

And then there's the issue that maybe the most straightforward thing to do is to unwind the recursion part but not all the way.

For example:

void traverse(Tree* p)
{
    if (p) {
        work_on(p);
        traverse(p->left);
        traverse(p->right);
    }
}

The second call to traverse is a tail recursion, which implies that it is probably a worthwhile optimization to rewrite it as an iteration:

void traverse(Tree* p)
{
    while (p) {
        work_on(p);
        traverse(p->left);
        p = p->right;
    }
}

The remaining call to traverse is not a tail recursion, so it is much harder to rewrite the code to eliminate it. It may well be that it is not worthwhile to do so.

This article has been dead for over six months. Start a new discussion instead.