Creating BST from sorted array in C++

Question

Can you help me understand why this code randomly results in memory access violation? Goal is to generate a binary search tree from sorted list.

Stepping through code I noticed a behavior where node pointer randomly changes when a recursive calls to fromSortedArray() function is returned. To give you a contex I am compiling this app using XCODE.

#include <iostream>
using namespace std;
class BST{
private:
    struct Node {
        int val;
        struct Node *left, *right;
    } *root;

public:
    BST(){
        this->root = NULL;
    }

    struct Node * fromSortedArray(int data[], int left, int right){
        if(left>right) return NULL;
        int m = left+(right -left)/2;
        struct Node *node = (struct Node *) malloc(sizeof(struct Node*));
        node->val = data[m];
        node->left = this->fromSortedArray(data, left, m-1);
        node->right = this->fromSortedArray(data, m+1, right);
        return node;
    }

    void fromSortedArray(int data[], int n){
        this->root = fromSortedArray(data, 0, n-1);
    }

    void deleteTree(struct Node *root){
        if(root==NULL) return;
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }

    void deleteTree(){
        this->deleteTree(this->root);
    }

    void traverse(struct Node *root){
        if(root == NULL) return;
        if(root->left!=NULL)traverse(root->left);
        printf("%d ", root->val);
        if(root->right!=NULL)traverse(root->right);
    }
    void traverse(){
        this->traverse(this->root);
    }

    ~BST(){
        deleteTree();
    }
};

int main(int argc, char * argv[]){
    BST tree;
    int data[] = {2,3,5,6,7,9};
    tree.fromSortedArray(data, 6);
    tree.traverse();
    cout << "\n";
    return 0;
}

score 2 · Answer 1 · answered Mar 07 '18 at 01:43

2

I think this line is wrong. struct Node *node = (struct Node *) malloc(sizeof(struct Node *));

should be sizeof(struct Node) becacuse you want to apply memory for Node not Node*

answered Mar 07 '18 at 01:43

hupodezhu

21
1

Thank you for the answer that helped to figure out the bug. – ramin Mar 07 '18 at 01:59

user4581301 · Accepted Answer · 2018-03-07T01:50:30.333

The Nodes are being malloced. One cannot combine malloc and delete. malloc must be matched with free and new must be matched with delete.

Avoid malloc. It gets you bytes of memory and nothing more, and you can easily miscalculate the number of bytes required. malloc should only be used in C++ in rare edge cases. More reading on the topic: In what cases do I use malloc vs new?

Use new instead of malloc and if at all possible, don't use new either. Use an Automatic variable, a library container, or a smart pointer instead.

This is a tree structure and, opinion here, so long as you observe the Rules of Three and Five you can get away with raw, stupid pointers because it's the the tree structure's job to handle the management of the nodes. That said, play around a bit with std::unique_ptr and std::make_unique when you get a chance. They can make your life easier.

Sticking with raw pointers for now, replace

struct Node *node = (struct Node *) malloc(sizeof(struct Node*));

with

Node *node = new Node;

Creating BST from sorted array in C++

2 Answers2