0

In the chapter on binary search tree's in CLRS and I encountered the transplant function which replaces a node u with node v with appropriate changes in the parent element. Here is the code I wrote for transplant function:

void transplant(Node* root, Node* u, Node* v)
{
    if(u->parent == NULL)
        root = v;
    else if(u == u->parent->left)
        u->parent->left = v;
    else
        u->parent->right = v;
    if(v != NULL)
        v->parent = u->parent;
}

It's not that I don't understand how this works but that why this works. When I make a function call I'm basically sending a copy of pointers root, u, v to the function right ? so the changes made in the function shouldn't actually reflect on the root unless I return it or use pointer to pointer type but its actually changing the original root. I defined root as global variable, does that change anything ?

8
  • How you call the function? And how is the root created? Sep 22, 2012 at 13:54
  • It shouldn't work if u is root, then you actually only change the local copy of root. In the other cases, you have pointers pointing to the actual Nodes and change those. Sep 22, 2012 at 13:55
  • i called the function as transplant(root, z, z->right) root is a pointer to a struct defined globally as Node* root = NULL
    – Aryan
    Sep 22, 2012 at 13:57
  • @Aryan Try calling it with transplant(root, root, root->right) and see whether root changes in main. Sep 22, 2012 at 14:05
  • @DanielFischer yes it did change root to NULL
    – Aryan
    Sep 22, 2012 at 14:09

1 Answer 1

0

The function will not work if u->parent is NULL, in that case, only the local variable root is set to v, nothing accessible from outside the function changes.

If u->parent != NULL, then u->parent->left and u->parent->right are the members of the Node pointed to by u->parent, and those are overwritten, so the changes are visible in main.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.