Where is the error in the tree program?

Question

Following are the two sample codes I had written in VS2008. The first sample code works fine, whereas the second(of a tree) gives some error.

 1)
#include<iostream>
using namespace std;

struct node{
        int number;
        struct node *right;
        struct node *left;
    }nodeType;

int insert(struct node *,int);

int main(){

        struct node * root=(struct node *)malloc(sizeof(node));
        root->left=NULL;
        root->right=NULL;
        root->number=10;
        insert(root,100);
      cout<<root->right->number; //This works fine

        return 1;
    }

int insert(struct node * leaf,int data){
        leaf->left =(struct node *)malloc(sizeof(node));
        leaf->right =(struct node *)malloc(sizeof(node));
        struct node *temp = leaf;
        temp->right->number=12;
        temp->left->number=11;
        temp->right->right=NULL;
        temp->right->left=NULL;
        temp->left->left=NULL;
        temp->left->right=NULL;
        return 1;
    }





  2)

#include<iostream>
using namespace std;
struct node{
    int number;
    struct node *right;
    struct node *left;
}nodeType;

int insert(struct node *,int);

int main(){

    int data[50];
    int i;
    for(i=0;i<50;i++){
     data[i]=rand()%100;
    }

    struct node * root=(struct node *)malloc(sizeof(node));
    root->left=NULL;
    root->right=NULL;

    root->number = 36;
    for(i=0;i<50;i++){
        insert(root,data[i]);
    }
    cout<<root->right->number; //This doesn't work, and it throws some memory error. Though it assigns a value(it is 41) which goes to the right side in the insert function, the root's right side pointer is not able to point into that memory location. Similar case with root->.... also.
    return 1;
}

int insert(struct node * leaf,int data){

    if(leaf==NULL){
        leaf = (struct node *)malloc(sizeof(node));
        leaf->number=data;
        leaf->left=NULL;
        leaf->right=NULL;
    }
    else if(data>=leaf->number){
        insert(leaf->right,data);
    }
    else if (data<leaf->number){
        insert(leaf->left,data);
    }
    else
    {

    }

    return 1;
}

Why in the second program it is not able to point into that location?

edit: The error which I got during runtime was:

Unhandled exception at 0x004114b4 in test.exe: 0xC0000005: Access vioation reading location 0x000000004.

Break Continue Ignore

Answer 1

@whozcraig did a right manly job of restraining himself. I have less self control, so I'm going to talk about some of the problems in your code you haven't noticed (or even seen symptoms of) yet.

First, you shouldn't normally use malloc in C++ code (nor struct xxx to define an instance of a struct, for that matter).

Second, you have code in both main and insert that's doing work that should really be handled by node's ctor (e.g., setting a node's child pointers to NULL).

Third, in insert you're testing a condition that can never be false, then adding an empty else that can never execute (but does nothing anyway).

I'd start by rewriting node to look something like this:

struct node{
    int number;
    node *right;
    node *left;

    node(int n) : number(n), right(NULL), left(NULL) {}
};

This way, the node's ctor initializes its child pointers to NULL, and puts the desired value into the node itself.

That lets us simplify the other code substantially. For example, insert ends up looking like this:

void insert(node *&leaf, int data){
    if (leaf == NULL)
        leaf = new node(data);
    else if (data < leaf->number)
        insert(leaf->left, data);
    else
        insert(leaf->right, data);
}

Since this is binary tree, there are really only three possibilities: 1) there is no "current" node -- in which case, we insert the new data "here", or 2) the new data belongs to the left of the current node, or 3) it belongs to the right of the current node. This code directly reflects that three-way decision process.

Quite a bit of the code in main seems unnecessary as well. For example, if we just want to insert some numbers into the tree, it's easy to simplify the code down to something like this:

node *root = NULL;

for (int i = 0; i < 50; i++)
    insert(root, rand() % 100);

There's no need to put the data into an array first -- we can put each item directly into the tree as it's generated.

Of course, to see what's going on, we probably want to print out not just one particular node in the tree, but (probably) all the data. Fortunately, that's pretty easy to do too:

void show(node *tree) {
    if (tree == NULL)
        return;
    show(tree->left);
    std::cout << "\t" << tree->number;
    show(tree->right);
}

This does a simple in-order traversal of the tree, printing each node as it's traversed. To avoid leaking the memory you created for the tree, you probably want to do something similar to delete the nodes in the tree. The major difference is that for this you probably want to do a post-order traversal (recursively delete both children, then delete the current node).

Another point is that a tree should really be a class of its own, with insert as a member function (and probably also a dtor to destroy a tree and delete all its contents, if you want something like the show above, perhaps an overload of operator<< to do that, etc.)

Answer 2

The second insert function is passing a node pointer by-value; not by reference or address. Therefore, modificaiton to it will not be carried outside of the function scope.

Change this:

int insert(struct node * leaf,int data)

To this:

int insert(struct node*& leaf,int data)

in both the prototype and the implementation.

Reserving all comments about the use of malloc() in a C++ program. As bad as it is, it has nothing to do with your problem.