Recursion: Returning a list in order traversal

Question

I have a basic function that does an in order traversal in C++:

void inorder(Node *root)
{
    if(root != NULL)
    {
       inorder(root->left);
       cout<<root->data<<endl;
       inorder(root->right);
    }
}

However, I would like to return a list as a result of this in order traversal. But the key thing is how can we determine when this recursive function actually ends and I can return the list. Here is the code that I've done so far;

vector<int> inorder(Node *root, vector<int> listToAdd)
{
    if(root != NULL)
    {
       inorder(root->left, listToAdd);
       listToAdd.push_back(root->data);
       inorder(root->right, listToAdd);

       //return here?
    }
    // return here?
}

I think the answer of this question would also help me with the core concept of recursion as well

Answer 1

The key thing is how can we determine when this recursive function actually ends

Like ordinary functions, recursive functions end as soon as the top level of its invocation returns. The problem with your function is that it tries to both construct a list, and return it; it should do one or the other.

Constructing the list is simple - make your function void, and change it as follows:

void inorder(Node *root, vector<int>& listToAdd)
{
    if(root != NULL)
    {
       inorder(root->left, listToAdd);
       listToAdd.push_back(root->data);
       inorder(root->right, listToAdd);
    }
}

That's it! The two changes I made was taking the argument by reference, and returning void. Call your function as follows:

vector<int> inorderList;
inorder(myNode, inorderList);

If you would like to return the list instead, you could modify your function as follows:

list<int> inorder(Node *node) {
    if (root != NULL) {
        list<int> lhs = inorder(node->left);
        list<int> rhs = inorder(node->right);
        copy(rhs.begin(), rhs.end(), back_insert_iterator<list<int> >(lhs));
        return lhs;
    } else {
        return list<int>();
    }
}

Note that the second alternative requires more copying.