c++vectorbinary-treepreorder

In my code for preorder traversal of binary tree, what is the reason for segmentation fault?


I have to return the elements of a binary tree in an int vector. I have written the following code, but it gives segmentation fault. What could be the reason for that? Also, does my code use correct logic?

struct Node
{    int data;
     struct *Node left;
     struct *Node right;
}
Node(int x)
{
     data = x;
     left = right = NULL;
}

vector <int> preorder(Node* root)
{
    vector <int> ans;
    if(root == NULL)
    {   
        return  {};
    }
    
    
    ans.push_back(root->data);
    ans.insert(ans.end(), preorder(root->left).begin(),preorder(root->left).end());
    ans.insert(ans.end(), preorder(root->right).begin(),preorder(root->right).end());
        
    
    return ans;

}

Solution

  • You are calling preorder twice for each ans.insert. They will return different vectors and their begin() and end() won't match. Therefore using them for specifying range is invalid.

    Instead of this:

    ans.insert(ans.end(), preorder(root->left).begin(),preorder(root->left).end());
    ans.insert(ans.end(), preorder(root->right).begin(),preorder(root->right).end());
    

    It should be:

    vector<int> left_res = preorder(root->left);
    ans.insert(ans.end(), left_res.begin(),left_res.end());
    vector<int> right_res = preorder(root->right);
    ans.insert(ans.end(), right_res.begin(),right_res.end());