CODEWITHSUNDEEP
c++algorithmrecursionbinary-search-tree
Ali
Ali

Reputation: 5476

Recursion: Returning a list in order traversal

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

Upvotes: 7

Views: 8660

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726579

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.

Upvotes: 10

tuckermi
tuckermi

Reputation: 879

If you place your return statement inside the body of the if, then you wouldn't hit a return statement in the case where root is null. That seems bad. Now, think about what happens if you put the return at the end of the function (outside of the conditional). Now, the return will be reached whether or not root is null, which is what you want.

That said, you should think about what happens when you make those two recursive calls. Are you depending on the recursive call to return a vector<int> that now has another item in it? If so, then you should probably be taking the value that is returned from the call to inorder and do something with it rather than just ignoring it. Hope that helps.

Upvotes: 0

Related Questions