Click here to Skip to main content
14,982,400 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
As far as I understood I think that when we pass a pointer to a function as its parameter, the operations performed by the function on that pointer parameter are directly done in the memory address where the pointer is pointing to.

But I'm not able to understand why this is not happening in the following code.

It seems the function is accepting the pointer parameter, then creating its own copy of the parameter, making all the changes in the local copy, and when it finishes the changes are lost.





I was learning about Binary Search Trees and implemented the BST myself before referring to how the instructor has done it. So I wrote the following code.

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

typedef struct bstNode {
    struct bstNode* left;
    int data;
    struct bstNode* right;
} bstNode_t;

bstNode_t* root = NULL;

bstNode_t* getNewNode(int data) {
    bstNode_t* newNode = (bstNode_t*)malloc(sizeof(bstNode_t));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

bstNode_t* insert(bstNode_t* root, int data) {
    if (root == NULL) {
        root = getNewNode(data); //This doesn't seem to attach root to pointer
        return root;
    } else if (data <= root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

int search(bstNode_t* root, int item) {
    if (root == NULL) {
        return 0;
    } else if (item == root->data) {
        return 1;
    } else if (item <= root->data) {
        return search(root->left, item);

    } else {
        return search(root->right, item);
    }
}

int main() {
    insert(root, 20); // This doesn't work
    insert(root, 10); // This doesn't work
    insert(root, 30); // This doesn't work
    printf("%d\n", search(root, 10)); // Output is 0
    printf("%d\n", search(root, 20)); // Output is 0
    printf("%d\n", search(root, 30)); // Output is 0
    printf("%d\n", search(root, 40)); // Output is 0

    return 0;
}



But when I referred to the Instructors code everything is still the same the only change is in the main() function as below.

C++
int main() {
    root = insert(root, 20); // This works
    root = insert(root, 10); // This works
    root = insert(root, 30); // This works
    printf("%d\n", search(root, 10));  // Output is 1
    printf("%d\n", search(root, 20));  // Output is 1
    printf("%d\n", search(root, 30));  // Output is 1
    printf("%d\n", search(root, 40));  // Output is 0

    return 0;
}


Now it seems confusing to me. Why do we have to save the returned address from the insert() method again when we already defined root as a global variable and also assigned the returned address to root in the insert() method already.

This is giving me an impression that in the insert() function when we write
root = getNewNode(data);
the function insert() creates a local copy of root and makes the changes in that local copy.


Totally confused. Can someone please explain to me, what is happening?

What I have tried:

I tried to debug the code to see what is happening internally and it seems that the root pointer is correctly attached to the pointer returned by insert() method until insert() is called again. As when it is called again it makes root() as NULL and starts from the if() statement where if(root==NULL) and the process repeats and I get all wrong output.
Posted
Updated 18-Mar-21 2:47am
Comments
11917640 Member 18-Mar-21 4:36am
   
Global variable is defined as bstNode_t*. Function is defined as search(bstNode_t* root) This function can change the data pointed by root parameter (such as int data), but not the pointer itself. To change the pointer, function parameter must be defined as bstNode_t** You may be confused also by the same parameter and global variable name. To understand this code better, rename root parameter to something else.
KarstenK 18-Mar-21 8:00am
   
this insert(bstNode_t* root, int data) declares the local var and so "hides" the global var.

You need a Pointer to Pointer or Reference to Pointer[^] to modify a pointer in a function, or else you are just modifying a local copy of the pointer.
   
Comments
Mohit Tomar 19-Mar-21 23:43pm
   
Thanks for posting the link. After reading, things are making more sense now.
First, don't use global variables (that is easily fixed).
In my opinion, the better solution, already suggested, is:
C
//..
int main()
{
    bstNode_t* root = NULL;
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    printf("%d\n", search(root, 10));
    printf("%d\n", search(root, 20));
    printf("%d\n", search(root, 30));
    printf("%d\n", search(root, 40));
    return 0;
}


The alternative producing clumsy code:
C
//..
bstNode_t* insert(bstNode_t** proot, int data)
{
    if (*proot == NULL)
    {
        *proot = getNewNode(data); //This doesn't seem to attach root to pointer
        return *proot;
    } else if (data <= (*proot)->data) {
        insert(&((*proot)->left), data);
    } else {
        insert(&((*proot)->right), data);
    }
    return *proot;
}
//.. 
int main()
{
    bstNode_t* root = NULL;
    insert(&root, 20);
    insert(&root, 10);
    insert(&root, 30);
    printf("%d\n", search(root, 10));
    printf("%d\n", search(root, 20));
    printf("%d\n", search(root, 30));
    printf("%d\n", search(root, 40));
    return 0;
}      
   
Comments
Mohit Tomar 19-Mar-21 8:23am
   
This approach is also good, and I don't think it is clumsy. In fact, there might be some situations where we have to pass a parameter to a function which is pointer to pointer. Thanks for posting. I find CodeProject more newbie-friendly as compared with StackOverflow.
CPallini 19-Mar-21 8:58am
   
You are welcome.
Indeed, while Stack Overflow provides reference answers to many questions, Code Project is by far more user friendly.
The problem is that your calls to the insert function pass a copy of the root pointer, which then becomes local to that function. So when the function sets the value of "root" to the address of the newly allocate buffer, it is using the local parameter. And when it returns from the function you forget to save the returned pointer. You can fix it in one of two ways:
C++
int main() {
    root = insert(root, 20); // save the returned pointer in the global variable
    root = insert(root, 10); // 
    root = insert(root, 30); // 

Or, change the insert function so it does not take a pointer as its first parameter:
C++
bstNode_t* insert(int data) {
    if (root == NULL) { // now refers to the global variable
        root = getNewNode(data);
        return root;
// ...

// 
int main ()
{
    insert(20); // save the returned pointer in the global variable
    insert(10); // 

Although the second version is much less clear. To be honest, there are very few reasons why using a global variable is a good idea. Your program would work just as well if root was a local variable inside main and you used the first form of code that I have shown.
   
Comments
KarstenK 18-Mar-21 8:02am
   
polite answer, but better is use of global ONLY WHEN NO OTHER SOLUTION is possible. It is a common origin of trouble.
Richard MacCutchan 18-Mar-21 8:07am
   
Yes, but as I suggested, like goto, it is rarely a good solution.
Mohit Tomar 18-Mar-21 8:26am
   
Yes correct. After investing 2 hrs I finally understood why it was not working in the first place. Thanks for your solution.

I'm new to C C++ and programming in general and use to think that when we pass a pointer variable to a function then the function would make the changes directly in the original pointer. Which turns out not to be correct.

So far I understood that if a function has a pointer parameter and a pointer variable is passed to it then both the original pointer variable and the pointer parameter of the function will point to the same memory location. While the function uses the local pointer for making changes to the memory it points to. Changes to its local pointer are lost after the function exits and we must collect the changes from the function after it completes and use that collected value in the original pointer that we passed to the function.

My god it took so long to finally make sense of how pointer and parameters work. I'm sure I won't make any mistakes going forward.
Richard MacCutchan 18-Mar-21 8:38am
   
Yes, pointers are wonderful things, but they do have a nasty habit of tripping you up sometimes.
This is expected in C++ because the local scope has higher priority. Read this short explanation.

That is one of the reasons global vars are bad and some naming conventions are making sense. So I wont the name root for a global var but name it globalRoot or better not use it at all.
   
Comments
Mohit Tomar 18-Mar-21 3:41am
   
Still not sure if I totally understand what is going on. The link you shared talks about local and global variables.

I understand how local and global variables behave. But what if our global variable is a pointer and the function also accepts the pointer and we are passing the pointer to the function as a parameter. This is what I did in the code above.

I don't think in the above case the global and local should make a difference as we are directly referring to the memory instead of calling the variables by name.

Still not clear.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900