Thread: Binary Tree C Tutorial

Hi there,

I am new to Binary trees and was studying them in the C tutorial. I am questioning the code posted in that tutorial as an example of inserting. I have marked the lines of code I am questioning with a '-':

Code:

insert(int key, struct node **leaf)
{
    if( *leaf == 0 )
    {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
-        (*leaf)->left->key_value = key;
        /* initialize the children to null */
-        (*leaf)->left->left = 0;    
-        (*leaf)->left->right = 0;  
    }
    else if(key < (*leaf)->key_value)
    {
        insert( key, &(*leaf)->left );
    }
    else if(key > (*leaf)->key_value)
    {
        insert( key, &(*leaf)->right );
    }
}

I think accessing the "left" pointer there is actually not initialized at that stage, possibly pointing to some unknown place or even NULL. I think the code should read:

Code:

-        (*leaf)->key_value = key;
        /* initialize the children to null */
-        (*leaf)->left = 0;    
-        (*leaf)->right = 0;

The reason is that "*leaf" is the pointer, and the "->" operator is referencing the object pointed to by "*leaf". Which is the newly created struct. The "left" pointer in the struct is not initialized yet, and it is being accessed.

Like I said, I am new to Binary Trees, so I could be wrong, but knowing pointers to pointers and reading this code, it looks incorrect to me.

Sincerely,
Daniel

I think you are right. It looks like a bad translation of the C++ version:

Code:

void btree::insert(int key, node *leaf)
{
  if(key< leaf->key_value)
  {
    if(leaf->left!=NULL)
     insert(key, leaf->left);
    else
    {
      leaf->left=new node;
      leaf->left->key_value=key;
      leaf->left->left=NULL;    //Sets the left child of the child node to null
      leaf->left->right=NULL;   //Sets the right child of the child node to null
    }  
  }
  else if(key>=leaf->key_value)
  {
    if(leaf->right!=NULL)
      insert(key, leaf->right);
    else
    {
      leaf->right=new node;
      leaf->right->key_value=key;
      leaf->right->left=NULL;  //Sets the left child of the child node to null
      leaf->right->right=NULL; //Sets the right child of the child node to null
    }
  }
}

This is the way the C version should look:

Code:

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

typedef struct node
{
    int key;
    struct node* left;
    struct node* right;
} node;

int insert(node** root, int key);
void dump(node* root);

int main()
{
    node* root = NULL;

    for (int x = 0; x < 10; ++x)
    {
        if (!insert(&root, rand() % 100))
            break;
    }

    dump(root);
}

int insert(node** root, int key)
{
    if (!*root)
    {
        *root = (node*)malloc(sizeof(node));

        if (!*root)
            return 0;

        (*root)->key = key;
        (*root)->left = NULL;
        (*root)->right = NULL;

        return 1;
    }
    else if (key < (*root)->key)
    {
        return insert(&(*root)->left, key);
    }
    else
    {
        return insert(&(*root)->right, key);
    }
}

void dump(node* root)
{
    if (root)
    {
        putchar('(');
        dump(root->left);
        printf("%d", root->key);
        dump(root->right);
        putchar(')');
    }
}

Code:

	*ptr2ptr = root;

Wrong... revise your pointer tutorial.

Originally Posted by danielpjdunbar

@Bayint Naung

How is it wrong?

You are dereferencing an uninitialized pointer. ptr2ptr is a reference to root and root is a reference to a node, so it should be

Code:

ptr2ptr = &root;

Since ptr2ptr is superfluous here, you can also do

Code:

insert(7, &root);

I also think the dereferencing there is not actually dereferencing the pointer (since it is a pointer to a pointer, not just a pointer)

A pointer to a pointer is still a pointer. Look closely at what your code does:

Code:

// ptr2ptr points to a random address
struct node **ptr2ptr;

...

// ptr2ptr is being dereferenced, but still points to a random address
*ptr2ptr = root;

It might work, but that does not mean it will always work. A pointer has to point to a valid address before it can be dereferenced, whether the thing at that address is another pointer or not.

You can see a version of it in this snippet from the insert function:

A precondition for insert() is that leaf is a valid pointer, so the dereference is assumed to be safe. In main() you guarantee that ptr2ptr is not a valid pointer and still dereference it.

@Inanna

A pointer to a pointer is handled slightly differently than just a pointer. You can see similar code here:
HowStuffWorks "How C Programming Works"
and here:
Chapter 22: Pointers to Pointers

In the HowStuffWorks page, it is saying that *ptr2ptr is a memory location controlled by the operating system, while ptr2ptr is a pointer controlled by the program.

I have done a quick program to check the memory addresses, and it appears that just declaring

Code:

int **ptr2ptr;

allocates 2 pointers. The first pointer (or the pointer to the pointer) is already initialized to the address of the other pointer. And that other pointer is initialized to 0. The way you set the value of the second pointer is by:

Code:

*ptr2ptr = &x;      // int x;

By just doing that you have the first pointer, ptr2ptr initialized with the address of *ptr2ptr, and now you have *ptr2ptr with the address of x.

Originally Posted by danielpjdunbar

I have done a quick program to check the memory addresses, and it appears that just declaring

Code:

int **ptr2ptr;

allocates 2 pointers. The first pointer (or the pointer to the pointer) is already initialized to the address of the other pointer. And that other pointer is initialized to 0. The way you set the value of the second pointer is by:

Code:

*ptr2ptr = &x;      // int x;

By just doing that you have the first pointer, ptr2ptr initialized with the address of *ptr2ptr, and now you have *ptr2ptr with the address of x.

I don't know what test you did, but either you misinterpreted it or you're using a slightly-off definition of "allocated". That declaration gives you space for just one pointer. Nothing is initialized to zero (unless you declare it at file scope rather than in a function). The expression "*ptr2ptr" just means "find the variable ptr2ptr, which contains an address, and then go to that address" -- it does not represent a separate piece of memory somewhere.

Originally Posted by danielpjdunbar

@Inanna

A pointer to a pointer is handled slightly differently than just a pointer. You can see similar code here:
HowStuffWorks "How C Programming Works"
and here:
Chapter 22: Pointers to Pointers

In the HowStuffWorks page, it is saying that *ptr2ptr is a memory location controlled by the operating system, while ptr2ptr is a pointer controlled by the program.

I have done a quick program to check the memory addresses, and it appears that just declaring

Code:

int **ptr2ptr;

allocates 2 pointers. The first pointer (or the pointer to the pointer) is already initialized to the address of the other pointer. And that other pointer is initialized to 0. The way you set the value of the second pointer is by:

Code:

*ptr2ptr = &x;      // int x;

By just doing that you have the first pointer, ptr2ptr initialized with the address of *ptr2ptr, and now you have *ptr2ptr with the address of x.

Adding a level of indirection does not change the rules. Pointers are very consistent. But you are always free to believe what you want, and I wish you the best of luck.

Originally Posted by tabstop

I don't know what test you did, but either you misinterpreted it or you're using a slightly-off definition of "allocated". That declaration gives you space for just one pointer. Nothing is initialized to zero (unless you declare it at file scope rather than in a function). The expression "*ptr2ptr" just means "find the variable ptr2ptr, which contains an address, and then go to that address" -- it does not represent a separate piece of memory somewhere.

Yes, the declaration does give one variable, ptr2ptr. It also gives it a value, some address. That address is of some other memory location, right - (It is pointing somewhere). That is the other piece of memory (that which variable ptr2ptr is addressing).

Originally Posted by Inanna

Adding a level of indirection does not change the rules. Pointers are very consistent. But you are always free to believe what you want, and I wish you the best of luck.

Yes, I agree with you that pointers are consistent. And I agree with you that *ptr2ptr is dereferencing ptr2ptr. The thing is that ptr2ptr is initialized to something by the operating system by just declaring it a pointer to a pointer.

Code:

  int **ptr2ptr;

Try this code:

Code:

	int **ptr2ptr;

	printf("\nThe first pointer contains %d",ptr2ptr);
	printf("\nThe second pointer exists at %d", &(*ptr2ptr));
	printf("\nThe second pointer contains %d", *ptr2ptr);

	printf("\nAllocating new memory cell");
	*ptr2ptr = (int *)malloc(sizeof(int *));

	printf("\nThe first pointer contains %d",ptr2ptr);
	printf("\nThe second pointer exists at %d", &(*ptr2ptr));
	printf("\nThe second pointer contains %d", *ptr2ptr);

        free(*ptr2ptr);

The output should be:
---
The first pointer contains 2130567168
The second pointer exists at 2130567168
The second pointer contains 0
Allocating new memory cell
The first pointer contains 2130567168
The second pointer exists at 2130567168
The second pointer contains 7278200
---