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