[crapmyster]

Hello, I'm having some problems with adding to the root node of a binary tree. I want to be able to check if the root node is NULL. If it is to add data to that node. However, it doesn't even get to inserting the data into the node as it thinks the root node is not NULL. If I take away this if statement it adds to the first node fine but I want to be able to check if the root node is NULL or not. Please can someone point me in the right direction.
Thanks, Mark.

#include <stdio.h>
#include <stdlib.h> 
typedef struct TreeNode 
{
        int item;         // The data in this node.
        struct TreeNode *left;   // Pointer to the left subtree.
        struct TreeNode *right;  // Pointer to the right subtree.
}TreeNode;
TreeNode *root = NULL;

struct TreeNode *insertion(int data)
{
    root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    TreeNode *current = root;
    if(current == NULL)
    {
        current->item = data;  
        current->left = NULL;
        current->right = NULL;
    }
}

void print(struct TreeNode *node)
{
        if(node == NULL)
        {
                return;
        }
        print(node->left);
        printf("%d ",node->item);
        print(node->right);

}

void menu()
{
        
	int temp = 1;
	while(temp == 1)
        {
                //Prints out the Menu
                int i;
                printf("");
                printf("*** Binary Tree Assignment ***\n");
                printf("Press 'i' to insert an element into the hash table\n");
                printf("Press 'd' to delete an element from the hash table\n");
                printf("Press 'l' to look up an element in the hash table\n");
                printf("Press 's' to obtain the size of the table\n");
                printf("Press 'p' to print the current table\n");
                printf("Press 'e' to exit from the program\n");
                printf("Enter a choice:\n");
		char input;
                scanf("%c", &input); //Getting user input for there selection
		switch(input)
		{
			//Insertion
			case 'i': printf("Type the integer you wish to enter into the hashTable:\n");	
                                  scanf("%d", &i);
                                  insertion(5);
				  break;
			//Deletion
			case 'd': printf("Type the integer you wish to delete from the hashTable:\n");
                                  scanf("%d", &i);
		        	  break;
			//Size
			case 's': 
				  break;
			//Print
			case 'p': print(root);
				  break;
			//Exit
                        case 'e': temp = 0;
                                  break;
			//If incorrect selection is made
			default:  printf("Error: Wrong selection, choose again\n");
				  break;
		}
        }
}

int main()
{
    menu();
    return 0;
}

[Skydiver]

The problem is due to line 13 of your code. You overwrite the NULL value that used to be in root with a newly allocated node. So by the time you copy the root pointer to current on line 14 and then check for NULL on line 15, it is too late.

[crapmyster]

Okay I understand what you are saying but how would I get round this. Can you point me in the right direction please.
Mark.

[Skydiver]

Pseudo-code:

allocate node
initialize node

if root is null then
    root = allocated node
else
    current = root
    walk down the tree to find insertion point
    insertion point = allocated node

[crapmyster]

Hello,

Don't worry I got it? Thanks for jogging my memory.
Solution:

#include <stdio.h>
#include <stdlib.h> 
typedef struct TreeNode 
{
        int item;         // The data in this node.
        struct TreeNode *left;   // Pointer to the left subtree.
        struct TreeNode *right;  // Pointer to the right subtree.
}TreeNode;
TreeNode *root = NULL;

struct TreeNode *insertion(int data)
{
    if(root == NULL)
    {
        root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->item = data;  
        root->left = NULL;
        root->right = NULL;
    }
}
     
void print(struct TreeNode *node)
{
        if(node == NULL)
        {
                return;
        }
        print(node->left);
        printf("%d ",node->item);
        print(node->right);

}

void menu()
{
        
	int temp = 1;
	while(temp == 1)
        {
                //Prints out the Menu
                int i;
                printf("");
                printf("*** Binary Tree Assignment ***\n");
                printf("Press 'i' to insert an element into the hash table\n");
                printf("Press 'd' to delete an element from the hash table\n");
                printf("Press 'l' to look up an element in the hash table\n");
                printf("Press 's' to obtain the size of the table\n");
                printf("Press 'p' to print the current table\n");
                printf("Press 'e' to exit from the program\n");
                printf("Enter a choice:\n");
		char input;
                scanf("%c", &input); //Getting user input for there selection
		switch(input)
		{
			//Insertion
			case 'i': printf("Type the integer you wish to enter into the hashTable:\n");	
                                  scanf("%d", &i);
                                  insertion(5);
				  break;
			//Deletion
			case 'd': printf("Type the integer you wish to delete from the hashTable:\n");
                                  scanf("%d", &i);
		        	  break;
			//Size
			case 's': 
				  break;
			//Print
			case 'p': print(root);
				  break;
			//Exit
                        case 'e': temp = 0;
                                  break;
			//If incorrect selection is made
			default:  printf("Error: Wrong selection, choose again\n");
				  break;
		}
        }
}

int main()
{
    menu();
    return 0;
}

[crapmyster]

Hello,

I'm running into some more trouble with this add method. Just trying to do the second part. I get an error something to do with not allocating memory or something like that on the line. Could you point me in the right direction please.

current->item = data;

struct TreeNode *insertion(int data, TreeNode *current)
{
    if(root == NULL)
    {
        root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->item = data;  
        root->left = NULL;
        root->right = NULL;
    }
    else
    {
        current = root;
        while(current != NULL)
        {
                if (data == current->item)
                {
                    printf("No Duplicate Values.");
                    return 0;
                }
                else if(data < current->item)
                {
                    current = current->left;
                }
                else if(data > current->item)
                {
                    current = current->right;
                }
        }
        current->item = data;
    }
}

[Skydiver]

Your loop on line 13 won't stop until current is null. On line 29, you are trying to use that null pointer.

[crapmyster]

Skydiver, on 12 November 2012 - 02:52 PM, said:

Your loop on line 13 won't stop until current is null. On line 29, you are trying to use that null pointer.

Surely I need that on line 29 so that data is added to that current node?

[jjl]

Quote

Surely I need that on line 29 so that data is added to that current node?

You are moving to a node that is a null pointer. You need to rethink your condition on line 13.

This post has been edited by jjl: 12 November 2012 - 04:53 PM

[crapmyster]

Still can't get it and confused. This is my thinking. You start at the root node and you add data to it. The if you want to add data which is smaller you go to the left subtree. So because I have defined current as equal to the root node I need to get to that left subtree node. So I do this;

current = current->left;

Since then I'm at the a node which is NULL I add data to this node like this:

current->item = data;

[Skydiver]

Consider the following tree:

     5
   /   \
  3     7
 / \   / \
N   N N   N

Root is pointing to the the 5, and you want to insert the value 2. N represents the NULL pointer value.

You'll start off with current pointing to 5. Since 2 is less than 5, you make current take what 5's left is pointing to. So now current is pointing to 3. Since 2 is less then 3, you make current point to what 3's left is pointing to, so current is now pointing to null.

You can't store 2 into null. What needs to happen is for you allocate a brand new node, store 2 into it, make 3's left point to that new node. You should end up with a tree that look like:

       5
     /   \
    3     7
   / \   / \
  2   N N   N
 / \
N   N

This post has been edited by Skydiver: 12 November 2012 - 05:28 PM