Inserting node into binary tree using pointers

Question

I'm trying to create a method for inserting nodes into a BST with the following structs:

// node structure
struct Node {
    int val;
    struct Node* left;
    struct Node* right;
};

// binary tree structure
struct BinaryTree {
    struct Node* root;
};

Originally I created this method for adding nodes to the tree:

// add value to binary tree
void _AddNode(struct Node* node, int val) {
    if (node == NULL)
        *(&node) = CreateNode(val);
    else if (val <= node->val)
        _AddNode(node->left, val);
    else
        _AddNode(node->right, val);
}
void AddNode(struct BinaryTree* tree, int val) {
    _AddNode(tree->root, val);
}

Using this function to construct the tree, I get a Segmentation fault: 11 error when I try to traverse, print, access data from the tree.

However, when I modified the function to pass in a double pointer and effectively do the same thing it worked:

// add value to binary tree
void _AddNode(struct Node** node, int val) {
    if (*node == NULL)
        *node = CreateNode(val);
    else if (val <= (*node)->val)
        _AddNode(&(*node)->left, val);
    else
        _AddNode(&(*node)->right, val);
}
void AddNode(struct BinaryTree* tree, int val) {
    _AddNode(&tree->root, val);
}

Why does the latter work, but the former doesn't.

For all sorts of graphs, my common advice is to use pen and paper to solve the most common problems. Draw a tree on paper, using small squares for the nodes, and write the value inside the squares, and then use arrows for the pointers. "Rearrange" the tree by erasing arrows and redrawing them. — Some programmer dude
– Some programmer dude, Commented Aug 5, 2019 at 18:43
In the "Originally I created" code *(&node) isn't right. node (as a parameter) is declared local to the function and is equivalent to simply node. — David C. Rankin
– David C. Rankin, Commented Aug 5, 2019 at 18:43
They are not the same -- in the first case you can't change the pointer and in the 2nd you can. — Hogan
– Hogan, Commented Aug 5, 2019 at 18:44
Sorry, I was looking at the "Originally I created" and should have been more clear. — David C. Rankin
– David C. Rankin, Commented Aug 5, 2019 at 18:45
Unrelated to your problem, but in C all symbols beginning with an underscore and followed by an upper-case letter (like _AddNode) are reserved. See e.g. this reserved identifier reference for details. — Some programmer dude
– Some programmer dude, Commented Aug 5, 2019 at 18:45

John Bollinger · Accepted Answer · 2019-08-05 19:09:02Z

1

However, when I modified the function to pass in a double pointer and effectively do the same thing it worked

Substantially the same thing, on fundamentally different data. The (&node) in your original attempt gives you a pointer to a local variable. When you dereference that and assign to the result, you are therefore modifying the local variable. Such a modification is not visible in any way to the caller.

On the other hand if you pass (say) a suitable double pointer to your function, say _AddNode(&(*node)->left, 42), then the value of the function parameter points to the same thing: the (*node)->left of the caller. If you dereference that pointer and assign to the result then naturally that is visible to the caller.

It seems that both the original and modified function are identical

Clearly, they are not lexically identical. You seem to mean that they appear to you to be equivalent, but since the difference in behavior disproves such an equivalence, it stands to reason that the manifest differences in the two functions in fact produce different semantics. The key thing that seems to have confused you is that in C, function arguments are always passed by value, so each function parameter starts with the value passed by the caller, but is not an alias for the caller's corresponding argument. Parameters of pointer type are no exception.

edited Aug 5, 2019 at 19:09

answered Aug 5, 2019 at 19:03

John Bollinger

191k11 gold badges103 silver badges206 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jay Mody Over a year ago

that makes a lot of sense, arguments that are passed to the function are local, so if I want to edit the value of a pointer I'd need to pass in the reference to that pointer (just like you would for a variable). Thanks!

John Bollinger Over a year ago

Yes, @JayMody, that's it exactly. And you seem now to have grasped a point that causes many people trouble: pointers are just another data type, and pointer values are just values of that type, thoroughly analogous in that sense to 42 as a value of type int.

Collectives™ on Stack Overflow

Inserting node into binary tree using pointers

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related