Root node in Binary search tree is null

Question

I am learning c++ and data structures I have implemented binary search tress can any body tell what is the issue in this code I am getting root pointer as null. Basically unable to create a tree. My final goal is to search the key in the tree. i have written a method for it. but unfortunately i am unable to create a tree. I have tested it by writing the traversal code.

#include <stdio.h>
#include <conio.h>
#include <iostream.h>

// Node structure
struct TreeNode {
    int value;
    int key;
    struct TreeNode *left;
    struct TreeNode *right;

   TreeNode()
    {
        left=NULL;
        right=NULL;
    }
};

void preOrder (TreeNode *);

void insertNode(TreeNode *, int, int);

TreeNode* findNode(TreeNode *aNode, int);

void main() {
    TreeNode *root = NULL;

    for(int i = 15; i<= 300; i+=15) {
        insertNode(root, i, i);

        if (root!=NULL) {
        cout<<root ->value<<endl;
        }
    }

    cout<<"The preorder traversal"<<endl;
    preOrder(root);

    getch();
}

void preOrder (TreeNode *p) {

    if (p!=NULL) {
        cout<<p ->value<<endl;
        preOrder(p ->left);
        preOrder(p ->right);
    }   else{
        cout << "NULL"<<endl;
    }
}

void createNewNode(TreeNode *newNode, int aValue, int aKey) {
    newNode = new TreeNode; // create new node
    newNode -> value = aValue; // set data
    newNode -> key = aKey; // set key
          cout<<newNode ->value<<endl;
    // Set left,right
    newNode -> left = newNode -> right = NULL;
}

void insertNode(TreeNode *aNode, int aValue, int aKey) {

    if (aNode == NULL) {
        TreeNode *newNode = new TreeNode; // create new node
        newNode -> value = aValue; // set data
        newNode -> key = aKey; // set key
        //createNewNode(newNode, aValue, aKey);

        if(newNode == NULL) {
            cout<< "Null returned"<<endl;
        } else {
             cout<< newNode -> key <<endl;
        }
        aNode = newNode;

    } else if (aKey == aNode->key) {
    cout<<aKey<<endl;
        return;

    } else if (aKey < aNode->key) {
          insertNode((aNode->left), aValue, aKey);

    } else {
        insertNode((aNode->right), aValue, aKey);
    }
}

TreeNode* findNode(TreeNode *aNode, int aKey) {

    if (aNode == NULL) {
        return NULL;
    } else if (aNode->key == aKey) {
         return aNode;
    } else if (aKey <= aNode->key) {
         return findNode(aNode->left, aKey);
    } else {
         return findNode(aNode->right, aKey);
    }
}

Answer 1

The problem is that your insertNode function attempts to create a new TreeNode if you pass in NULL, but this doesn't affect the pointer you've passed in.

For example,

void foo(int * p) {
    p = new int;
}

int main() {
    int* test = NULL;
    foo(test);
    // test is still NULL, but foo created an int internally
}

What you need to do, is pass your pointer in as a reference, so that foo will modify the pointer you're giving it (rather than just creating one). Like this:

void foo(int *& p) { // Notice I'm now using a reference to a pointer
    p = new int;
}

int main() {
    int* test = NULL;
    foo(test);
    // test will now point to whatever foo created
}

I think you'll learn best if you now try to apply this to your example. Try to understand exactly why this needs to be done. Just ask if you need more clarification.

Answer 2

The main problem according to me in your insert node code, you are passing aNode by call by value instead of call by reference. Instead of using just TreeNode *aNode in your insert node function, try using TreeNode * &aNode.