C++ Binary Search Tree Insertion functions

Question

Helly everyone,

I took a C++ coding course with practically no prior knowledge(my understanding of pointers is still somewhat shakey)at University this semester. I have to implement a binary search tree in C++ and my problem is as follows: Over a predefined Node structure with values and pointers to a left and a right node I am supposed to implement several functions, two of them being:

void InsertNode(Node* root, Node* node)

which is supposed to fit the handed node into the given tree "root", and another one called

void InsertValue(Node* root, int value)

which should create a new instance of the node struct with the passed value and fit it in the given tree "root". To do so I am supposed to use both CreateNode (simple function to create Node* pointer of a new Node instance with int value and left/right pointers set to NULL) and InsertNode.

Im kind of running in a treadmill here and i dont think i really understand how the functions are supposed to work(eg. the difference between them). Yesterday i wrote this function:

void InsertNode(Node* root, Node* node){
    if(root == NULL){
        root = CreateNode(node->value);
    }
    else if(root->value < node->value){
        if(node->left != NULL){
             InsertNode(root, node->left);
        }
        else{
             node->left = CreateNode(root->value);
        }
    }
    else if(root->value > node->value){
        if(node->right != NULL){
             InsertNode(root, node->right);
        }
        else{
            node->right = CreateNode(root->value);
        }
    }
}

Since im not really able to test these functions without the later functions that will actually build the tree with given nodes i was curious if i could get some help here with the next functions InsertValue(what is it supposed to do that InsertNode doesnt do already? :S)

Greetings and thanks in advance.

Solution 1

Initial note: This answer assumes that the InsertNode function is initially called with root being the root of the tree, and node being the node to insert into the tree.

---

One problem is this statement:

root = CreateNode(node->value);

Since the argument root is passed by value, which means that it is copied, the assignment will only change the local copy. Once the function returns the original pointer that you pass to the function will not have changed.

You need to pass the pointer by reference, meaning the root argument references the original variable passed in to the function, instead of it being copied. You do this by using an ampersand when declaring the argument:

Node*& root

The above means that root is a reference to a pointer to Node.

So the complete InsertNode declaration should look like

void InsertNode(Node*& root, Node* node)

---

There are also other problems, for example these lines are not correct:

if(node->left != NULL){
     InsertNode(root, node->left);
}
else{
     node->left = CreateNode(root->value);
}

This is not correct because node->left should be NULL always, which makes you create a new node using the value from the root of the tree, and assign it to node->left, but you never insert node in the tree.

What you should instead do is simply

InsertNode(node->left, node);

Of course you should do the same change for setting the right branch.

---

Combining the two solutions above, your function would look like

void InsertNode(Node*& root, Node* node)
{
    if (root == 0)
        root = node;
    else if (root->value < node->value)
        InsertNode(root->left, node);
    else
        InsertNode(root->right, node);
}

This function also solves a third problem with your current code: What if node->value is equal to root->value? The above function puts it in the right branch.

Solution 2

When you are creating a tree, value are also assigned with each node. See following code:

typedef struct BST {
   int data;
   struct BST *lchild, *rchild;
} node;


void insert(node *root, node *new_node) {
   if (new_node->data < root->data) {
      if (root->lchild == NULL)
         root->lchild = new_node;
      else
         insert(root->lchild, new_node);
   }

   if (new_node->data > root->data) {
      if (root->rchild == NULL)
         root->rchild = new_node;
      else
         insert(root->rchild, new_node);
   }
}

node *new_node, *root;

int main()
{ 
        new_node = get_node();
        printf("\nEnter The Element ");
        scanf("%d", &new_node->data);

        if (root == NULL) /* Tree is not Created */
           root = new_node;
        else
           insert(root, new_node)
}