Using Pointer to Pointer of Struct while adding nodes in the binary tree

Question

I want to know the reason why do we use, pointer to pointer while inserting nodes in the binary tree. But, While traversing the binary tree, we just refer the tree by simple pointer to the root node. But why while inserting node?

Can anyone help me in providing the reason or reference link to understand why it is pointer to pointer .

/*This program clears out all the three methods of traversal */

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

/* Let us basically describe how a particular node looks in the binary tree .... Every node in the tree has three major elements , left child, right child, and  and the data. */

struct  TreeNode {
int data;
struct TreeNode *leftChild;
struct TreeNode *rightChild;
};

void inorder(struct TreeNode *bt);
void preorder(struct TreeNode *bt);
void postorder(struct TreeNode *bt);
int insert(struct TreeNode **bt,int num);

main()
{
int num,elements;
struct TreeNode *bt;
int i;

printf("Enter number of elements to be inserted in the tree");
scanf("%d",&num);

printf("Enter the elements to be inserted inside the tree");
for(i=0;i<num;i++)
{
scanf("%d",&elements);
insert(&bt,elements);
printf("\n");
}

printf("In Order Traversal \n");
inorder(bt);

printf("Pre Order Traversal \n");
preorder(bt);

printf("Post Order Traversal \n");
postorder(bt);

return 0;
}

int insert(struct TreeNode **bt,int num)
{
if(*bt==NULL)
{
*bt= malloc(sizeof(struct TreeNode));

(*bt)->leftChild=NULL;
(*bt)->data=num;
(*bt)->rightChild=NULL;

return;
}
else{
/* */
if(num < (*bt)->data)
{
insert(&((*bt)->leftChild),num);
}
else
{
insert(&((*bt)->rightChild),num);
}
}
return;
}

void inorder(struct TreeNode *bt){
if(bt!=NULL){


//Process the left node
inorder(bt->leftChild);

/*print the data of the parent node */
//printf(" %d ", bt->data);

/*process the right node */
inorder(bt->rightChild);
}

}

void preorder(struct TreeNode *bt){
if(bt)
{
//Process the parent node first
printf("%d",bt->data);

//Process the left node.
preorder(bt->leftChild);

//Process the right node.
preorder(bt->rightChild);


}

}


void postorder(struct TreeNode *bt){

if(bt)
{
//process the left child
postorder(bt->leftChild);

//process the right child
postorder(bt->rightChild);


//process the parent node
printf("%d",bt->data);


}
}

yup got it .. my vi editor was in one color .. wasnt able to figure that out.. but still the question pointer to pointer remains unsolved — Nilesh Agrawal
– Nilesh Agrawal, Commented Jun 20, 2013 at 17:28
well now it is running code !! still i am unable to figure out y it is pointer to pointer while inserting nodes.. can anyone provide reference. or reason for it — Nilesh Agrawal
– Nilesh Agrawal, Commented Jun 20, 2013 at 17:41
So, when we pass a pointer, we can change only data it points. When we use pointer to pointer we can change address it points. — awesoon
– awesoon, Commented Jun 20, 2013 at 17:45

Mike · Accepted Answer · 2013-06-20 17:48:32Z

"I want to know the reason why do we use, pointer to pointer while inserting nodes in the binary tree. But, While traversing the binary tree, we just refer the tree by simple pointer to the root node. But why while inserting node?"

We actually don't even need the code to answer this. If you want to modify (write to) data in an external function in C, you need to have the address of the data. Just like:

main() {
   int x = 2;
   change_me(x);
   printf("%d\n", x); // prints 2
}

void change_me(int x){
   x++;
}

has no meaning. You're (in this example) getting a local copy of the vairable, any changes made to the value are only within the local scope. If you want those changes to propagate back to the calling function you need the address:

main() {
   int x = 2;
   change_me(&x);
   printf("%d\n", x); // prints 3
}

void change_me(int* x){
   (*x)++;
}

The same applies to pointers. In the example of a linked list, if I want to print the values, I need to traverse the tree and read data. I don't need to change anything so just the pointer will do. However if I want to modify the tree:

struct node{
   int val;
   sturct node* next;
};

main() {
  struct node* head = malloc(sizeof(struct node));
  head->val = 3;
  insert_a_node_in_front(head);
}

insert_a_node_in_front(node * ptr) {
    struct node* temp = ptr;
    ptr = malloc(sizeof(struct node));
    ptr->val = 5;
    ptr->next = temp;
}

Well, guess what? We didn't actually just insert that node because head's value never changed. It's still pointing to the original node with a val==3. The reason is the same as before, we tried to change the value of the local copy of the parameter. If we want those changes to stick it needs the address of the original copy:

  insert_a_node_in_front(&head);
}

insert_a_node_in_front(node ** ptr) {
    struct node* temp = (*ptr);
    (*ptr) = malloc(sizeof(struct node));
    (*ptr)->val = 5;
    (*ptr)->next = temp;
}

Nigel Harper · Accepted Answer · 2013-06-20 17:48:01Z

2

It's because of the first part of insert where it mallocs a new struct treenode. If you only passed in a struct treenode * this would look something like this:

int insert(struct TreeNode *bt,int num)
{
   if(bt==NULL)
   {
       bt= malloc(sizeof(struct TreeNode));

       (bt)->leftChild=NULL;
       (bt)->data=num;
       (bt)->rightChild=NULL;

   return;
   }
  ...
}

The problem with that would be that bt is local to insert so the bt in main would be unchanged. So you pass in a pointer to main's bt, which allows insert to change it.

answered Jun 20, 2013 at 17:48

Nigel Harper

1,2509 silver badges13 bronze badges

Comments

Nilesh Agrawal · Accepted Answer · 2013-06-27 15:02:22Z

1

a very good tips on using pointer is given here : Try this basics : -

http://www.geeksforgeeks.org/how-to-write-functions-that-modify-the-head-pointer-of-a-linked-list/

answered Jun 27, 2013 at 15:02

Nilesh Agrawal

3,09211 gold badges29 silver badges57 bronze badges

Collectives™ on Stack Overflow

Using Pointer to Pointer of Struct while adding nodes in the binary tree

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related