Altering a struct that has been passed by caller? (constructing binary search tree from preorder)

Question

I have programmed in Java for a few years now, and I am attempting to learn C++.

I would like some tips about what is wrong with this piece of code specifically, but more importantly, I'd like to know whether I am approaching this question correctly or not. The task is to return TreeNode *root to a BST, given vector<int>& preorder.

The general idea is clear to me: recursively find left and right bounds, and build the tree using this.

I have tried:

1. using a helper method that returns a TreeNode * - this caused AddressSanitizer: heap-buffer-overflow errors

2. converting the helper method to return type void, and passing a TreeNode *ptr as a parameter - this causes runtime error: member access within null pointer of type 'TreeNode' errors

My code:

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode();
        constructSubtree(preorder, root, 0, preorder.size());
        return root;
    }
private:
    void constructSubtree(vector<int>& preorder, TreeNode* ptr, int start, int end) {
        if(start == -1 || start >= end) {
            return;
        }
        ptr->val = preorder[start];
        int split = -1; // first idx where preorder[idx] > preorder[start]
        for(int i = start + 1; i < end; ++i) {
            if(preorder[i] > preorder[start]) {
                split = i;
                break;
            }
        }
        constructSubtree(preorder, ptr->left, start + 1, split);
        constructSubtree(preorder, ptr->right, split, end);
    }
};

some example input: [8,5,1,7,10,12]

Can someone explain what I'm doing wrong?

As I said, I am still learning C++, and I would also really like to hear general tips about working with pointers (and who is responsible for freeing their content).

Answer 1

ptr of constructSubtree() should be allocated before call, because it's not allocated in the function. so you should allocate ptr->left and ptr->right before call the function constructSubtree() recursively. below is working code(though not so neat)

class   TreeNode
{
public:
    TreeNode() { val = 0; left = nullptr; right = nullptr; }
    int val;
    TreeNode    *left;
    TreeNode    *right;

    void    print()
    {
        if(left != nullptr)
            left->print();
        std::cout << val << std::endl;
        if(right != nullptr)
            right->print();
    }

    void    remove()
    {
        if(left != nullptr)
            left->remove();
        if(right != nullptr)
            right->remove();
    }
};

class Solution {
public:
    TreeNode* bstFromPreorder(std::vector<int>& preorder) {
        constructSubtree(preorder, &root, 0, preorder.size());
        return root;
    }
private:
    TreeNode    *root;
    void constructSubtree(std::vector<int>& preorder, TreeNode** ptr, int start, int end) {
        if(start == -1 || start >= end) {
            return;
        }
        *ptr = new TreeNode();
        (*ptr)->val = preorder[start];
        int split = -1; // first idx where preorder[idx] > preorder[start]
        for(int i = start + 1; i < end; ++i) {
            if(preorder[i] > preorder[start]) {
                split = i;
                break;
            }
        }
        if(split != -1)
        {
            constructSubtree(preorder, &((*ptr)->left), start + 1, split);
            constructSubtree(preorder, &((*ptr)->right), split, end);
        }
    }
};