Where am I doing wrong for inserting node to a binary tree?

Question

I do research in stackoverflow and can not find out where am i doing wrong. Codes that I found are similiar to mine. I have difficulties on coding AddNodeToTree function. When I run this code its output always first item of the tree. I want to code it Iteratively. Could you help me what am I missing? Thanks.

Here is my code.

#include <stdio.h>
#include <stdlib.h>

typedef struct _Node{

    int data;
    struct _Node* left;
    struct _Node* right;
}Node;


void* AllocateMemory(size_t size){

    void* pvMem;

    pvMem=malloc(size);

    if(pvMem==NULL){
        fprintf(stderr,"Cannot Allocate Memory!");
        exit(EXIT_FAILURE);
    }

    return pvMem;

}

Node* NewNode(int data){

    Node* new_node;

    new_node = AllocateMemory(sizeof(Node));

    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;

    return new_node;
}

Node* AddNodeToTreeRecursive(Node* root, int data){

    if(NULL==root)
        return (NewNode(data));

    if(root->data > data)
        root->left = AddNodeToTreeRecursive(root->left, data);
    else if(root->data < data)
        root->right = AddNodeToTreeRecursive(root->right, data);

    return root;

}

void PrintList(Node* root){

    if(root==NULL)
        return;

printf("DATA: %d\n", root->data);

    PrintList(root->left);

    PrintList(root->right);


}


Node* AddNodeToTree(Node* root, int data){

    Node* new_item = NewNode(data);
    Node** temp = &root;

    if(root==NULL)
        return new_item;

    while(*temp!=NULL){

        if((*temp)->data > data)
            temp = &(*temp)->left;

        else if((*temp)->data <= data)
            temp = &(*temp)->right;

    }

    *temp = new_item;


    return root;
}


int main()
{

    Node* root=NULL;

    root=AddNodeToTree(root, 30);
    root=AddNodeToTree(root, 20);
    root=AddNodeToTree(root, 10);
    root=AddNodeToTree(root, 1);
    root=AddNodeToTree(root, 5);
    root=AddNodeToTree(root, 3);
    root=AddNodeToTree(root, 7);

    PrintList(root);

    return 0;
}

Answer 1

temp = new_item; doesn't do what you think it does. All it does is to reassign the local variable temp to something else. It doesn't change the pointer you copied it from.

Think of Node as a person and each hand of that person (which can point to another person) being the left and right pointers respectively. Now your tree is a whole network of people pointing to each other. Then temp is someone else' hand, repeatedly pointing to different people, until he/she ends up pointing at nothing. Then you tell him/her to point to someone else (new_item), which obviously won't change your network of people pointing at each other, since temp isn't part of this network.

The simplest fix I can think of is to make temp a Node**:

Node** temp = &root;

// your code to traverse the tree, except that you should
// replace `temp = ...` with `temp = &...`
//   and every other occurrence of `temp` with `*temp`

*temp = new_item;

To extend the metaphor, temp would then be pointing to a hand rather than a person, and changing *temp would involve making that hand point to another person. Since that hand is part of the network, changing it would change the network.

Answer 2

This looks fishy in AddNodeToTree

while(temp!=NULL){

    if(temp->data > data)
        temp = temp->left;

    else if(temp->data <= data)
        temp = temp->right;

}

The reason is: temp the root. You passed it in as a pointer.

You are setting it to be the left or right node.

You are returning root, but you modified it by modifying temp.