Problem with adding to a binary tree

Page 1 of 1

10 Replies - 3221 Views - Last Post: 12 November 2012 - 05:27 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=299833&amp;s=da1fa9a8c1388bc73fa1abeb9f3c8287&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 crapmyster

Reputation: 0
• Posts: 78
• Joined: 12-October 11

Problem with adding to a binary tree

Posted 12 November 2012 - 10:05 AM

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);

}

{

int temp = 1;
while(temp == 1)
{
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;
default:  printf("Error: Wrong selection, choose again\n");
break;
}
}
}

int main()
{
return 0;
}

```

Is This A Good Question/Topic? 0

Replies To: Problem with adding to a binary tree

#2 Skydiver

• Code herder

Reputation: 6111
• Posts: 21,035
• Joined: 05-May 12

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 10:26 AM

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.

#3 crapmyster

Reputation: 0
• Posts: 78
• Joined: 12-October 11

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 10:36 AM

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

#4 Skydiver

• Code herder

Reputation: 6111
• Posts: 21,035
• Joined: 05-May 12

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 10:40 AM

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

```

#5 crapmyster

Reputation: 0
• Posts: 78
• Joined: 12-October 11

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 10:43 AM

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);

}

{

int temp = 1;
while(temp == 1)
{
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;
default:  printf("Error: Wrong selection, choose again\n");
break;
}
}
}

int main()
{
return 0;
}

```

#6 crapmyster

Reputation: 0
• Posts: 78
• Joined: 12-October 11

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 02:42 PM

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;
}
}

```

#7 Skydiver

• Code herder

Reputation: 6111
• Posts: 21,035
• Joined: 05-May 12

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 02:52 PM

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

#8 crapmyster

Reputation: 0
• Posts: 78
• Joined: 12-October 11

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 04:01 PM

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?

#9 jjl

• Engineer

Reputation: 1270
• Posts: 4,998
• Joined: 09-June 09

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 04:05 PM

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

#10 crapmyster

Reputation: 0
• Posts: 78
• Joined: 12-October 11

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 04:36 PM

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;

```

#11 Skydiver

• Code herder

Reputation: 6111
• Posts: 21,035
• Joined: 05-May 12

Re: Problem with adding to a binary tree

Posted 12 November 2012 - 05:27 PM

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