push_back() is not adding element to the vector? (C++ Tree Traversal)

March 2, 2022

I’m working through a tree traversal problem and using ‘push_back’ vector function to update a vector with the in-order traversal. Alongside using this I am using cout to print out the solution to debug. The print output is correct but my returning vector doesn’t match the print so I can only put this down to me not understanding how the push_back function works.

This is the function I am using:

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> order {};
        if (root != nullptr) {
            inorderTraversal(root->left);
            cout << "pushing back : " << root->val << std::endl; 
            order.push_back(root->val);
            inorderTraversal(root->right);
         } 
        
        return order;
    }

For the input tree [1,null,2,3] My stdout is printing:

pushing back : 1
pushing back : 3
pushing back : 2

Which is correct but my returning array (order) is only [1].

>Solution :

You’re ignoring the results from each recursion. You should be doing this:

vector<int> inorderTraversal(TreeNode *root)
{
    vector<int> order;
    if (root != nullptr)
    {
        order = inorderTraversal(root->left);
        cout << "pushing back : " << root->val << std::endl;
        order.push_back(root->val);
        auto tmp = inorderTraversal(root->right);
        order.insert(order.end(), tmp.begin(), tmp.end());
    }

    return order;
}