Traversals through Tree.. In order problem with memory access violation

Question

So I wrote up this little peace of code as practice for myself...

But i am getting in travers_inorder function at line *traverse_inorder(p->left)* memory access violation and program crashes. Why??? Any ideas?

UPDATE: I am using visual studio 2008 SP1 an visual C++ compiler

#include <iostream>
#include <time.h>

using namespace std;

struct tree_node
{
tree_node *left;
tree_node *right;
int value;
};
void populate_rnd_tree(tree_node *root, int cnt);
void traverse_inorder(tree_node *p);

int main()
{
srand(time(NULL));
tree_node * nTmp = new tree_node;

populate_rnd_tree(nTmp, 10);

traverse_inorder(nTmp);

return 1;
}

void populate_rnd_tree(tree_node *root, int cnt)
{
tree_node *old = root, *left, *right;

left = new tree_node;
right = new tree_node;

int val = 0;
// exit condition
if (cnt == 0) return;

val = rand()%50;
old->value = val;
old->left = left;
old->right = right;

populate_rnd_tree(left, cnt-1);
populate_rnd_tree(right, cnt-1);

return;
}

void traverse_inorder(tree_node *p)
{ 
if (p != NULL)
{
    traverse_inorder(p->left);
    cout << p->value << endl;
    traverse_inorder(p->right);
}
} 

Answer 1

My best guess: looks like you never actually set your final child nodes to NULL in your tree generation procedure. As such, your conditional to stop traversing is never hit, as left and right are just uninitialized pointers. In populate_rand_tree, do the following:

if (cnt == 0) 
{
    old->left = NULL;
    old->right = NULL; 
    return;
}

Alternatively, since you are using C++...

struct tree_node
{
    tree_node() : left(NULL), right(NULL) { }

    tree_node *left;
    tree_node *right;
    int val;
}