inorder to bst from a normal tree

Question

why is the first written code generating error while second doesnt . what i dont get is that in both the codes we are manipulating the root pointer then why is it that first one doesnt work but second one does (vector is inorder traveral of a normal bst) //code1 (showin segmentation fault

Node* makebst(Node* &root, vector<Node*> &vect, int start, int end){
    if(start>end){
        return NULL;
    }
    root=vect[((start+end)/2)+1];
    root->left=makebst(root->left, vect, start, (start+end)/2);
    
    root->right=makebst(root->left, vect, ((start+end)/2)+2, end);
    return root;
}
//code 2(corrected by chatgpt that actually worked
Node* makebst(Node* &root, vector<Node*>& vect, int start, int end) {
    if (start > end) {
        return NULL;
    }
    int mid = (start + end) / 2;
    root = vect[mid];
    root->left = makebst(root->left, vect, start, mid - 1);
    root->right = makebst(root->right, vect, mid + 1, end);
    return root;
}

code 1 was written by me at first but its not working i dont get it why

Answer 1

When start and end are equal, the expression ((start+end)/2)+1 will return end+1, which is outside of the start..end (inclusive) range.

That is a two-fold problem:

• when end is the last valid index of the vector, this access in vect leads to undefined behaviour, which can be a segmentation error. This scenario happens when the vector has a size of 1.

• when end is not the last valid index of the vector this leads to a recursive call that has the same values for start and end, leading to infinite recursion and eventually a stack limit overrun.

The corrected code uses an expression for mid that is guaranteed to stay within the limits of start and end.

A second issue (unrelated to your question) is that your code never does anything with root->right.