Pointer to pointer doesn't work in tree copying algorithm

Question

I'm trying to write a tree copy function in C:

void tree_copy(treenode *source, treenode **dest)
{
    treenode *newtree;      //the new tree will be created using this as root   
    treenode **bkup = &newtree;         //pointer to pointer, to keep backup of head of newtree

    /*
    Code to create new tree
    Traverses using *newtree
    And leaves *newtree pointing at last node created
    But *bkup still contains the address of the head node, right?
    */

    *dest = *bkup;  //assign the new tree created to the parameter
}

//I'm trying to invoke it like this:

int main(void)
{
    treenode *t1, *t2;

    create_tree(&t1);   //tested, already written function to create a tree. No bugs.
    tree_copy(t1, &t2);

    preorder(t2);       //tested, already written function for preorder traversal.
}

The node supposed to contain the newly created tree's root (t2) still remains NULL after this operation. Why is this happening? What is wrong in my logic in backing up the starting node of new tree?

Any help will be greatly appreciated.

score 1 · Accepted Answer · answered Oct 15 '15 at 05:25

1

treenode *newtree;
treenode **bkup = &newtree;

bkup contains the address of the newtree variable. The newtree variable will contain the address of a treenode.

So bkup doesn't contain a copy of the pointer stored in newtree, it contains the address of the newtree variable. Storing that is not really helpful, since it won't change anyway. The newtree variable will stay in the same place, no matter what content you assign to it.

If you want to save a copy of the initial value of newtree, you have to copy that to a newtree* variable once it got initialized:

treenode *root = newtree;
...
*dest = root;

answered Oct 15 '15 at 05:25

sth

222,467
53
283
367

"So bkup doesn't contain a copy of the pointer stored in newtree, it contains the address of the newtree variable. Storing that is not really helpful, since it won't change anyway." True, but if you notice in the code, while returning, I am **dereferencing** `bkup`. So it should now provide the address of the original `newtree` node, right? If there is something I am missing, can you please edit your answer to show a diagram? – aditya_medhe Oct 15 '15 at 05:34
`bkup` contains the address of `newtree`, so dereferencing it yields the contents of that memeory at that address, the contents of the `newtree` variable. `*bkup` just means "look over there, in the `newtree` variable". It will give you the current content of that variable, not some old version of it. If you assign something new to `newtree` then content in its memory location changes, and if you look at the memory location again with `*bkup` you will see the new content. `bkup == &newtree`, so `*bkup == *&newtree` (`== newtree`) – sth Oct 15 '15 at 05:48
Ah, got it. Thanks for your answer and the explanation. – aditya_medhe Oct 15 '15 at 05:52

score 0 · Answer 2 · answered Oct 15 '15 at 05:15

0

 treenode *newtree;      //the new tree will be created using this as root   
    treenode **bkup = &newtree;         //pointer to pointer, to keep backup of head of newtree //

newtree is a pointer which is uninitialized and you are using the address of an uninitialized variable which will lead to undefined behavior

answered Oct 15 '15 at 05:15

Gopi

19,784
4
24
36

Thanks for your answer, but I fail to understand this. I have stored the **address** of `newtree` in `bkup`. Now I start with creating a new tree with `newtree` as head. So now `*bkup` should contain the head of the new tree, right? – aditya_medhe Oct 15 '15 at 05:26
I don't think taking the address of an uninitialized variable is undefined behavior. See for example http://stackoverflow.com/questions/28587022/is-it-undefined-behavior-to-take-the-address-of-an-uninitialized-pointer – sth Oct 15 '15 at 05:36

Pointer to pointer doesn't work in tree copying algorithm

2 Answers2