c++ - Recursion: Returning a list in order traversal -

i have basic function in order traversal in c++:

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

however, return list result of in order traversal. key thing how can determine when recursive function ends , can return list. here code i've done 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 answer of question me core concept of recursion well

the key thing how can determine when recursive function ends

like ordinary functions, recursive functions end top level of invocation returns. problem function tries both construct list, , return it; should 1 or other.

constructing list simple - make function void, , change 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! 2 changes made taking argument reference, , returning void. call function follows:

vector<int> inorderlist; inorder(mynode, inorderlist); 

if return list instead, modify function 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 second alternative requires more copying.