Basic question in binary tree node insertion

[Indrajeet]

I was looking at this function segment that inserts a node into a
binary tree :

void insert(Tree** pRoot, int n)
{
if (*pRoot != NULL)
{
if ((*pRoot)->val > n)
insert(&((*pRoot)->left),n);
else
insert(&((*pRoot)->right),n);
}
else
{
Tree* new = (Tree *)malloc(sizeof(Tree*));
new->val = n;
new->left = NULL;
new->right = NULL;
*pRoot = new;
}
}

main() makes successive calls to insert as in insert(&root,35); insert
(&root, 37); insert(&root, 39);
A preOrder listing as in preOrder(&root) prints correctly.

Since 39 is the last created node and the line in insert() goes
"*pRoot = new", would this not alter the variable root in main() to
point to the node that holds the last added value, viz. 39? Pardon me
if my understanding of pointers is fuzzy, I'd be much grateful for an
explanation showing where my understanding has got holes, obviously
I've got some way to go

 

[Nick Keighley]

I was looking at this function segment that inserts a node into a
binary tree :

void insert(Tree** pRoot, int n)
{
    if (*pRoot != NULL)
    {
        if ((*pRoot)->val > n)
        insert(&((*pRoot)->left),n);
        else
        insert(&((*pRoot)->right),n);
    }
    else
    {
        Tree* new = (Tree *)malloc(sizeof(Tree*));

this isn't right. You want the size of Tree not the size of Tree*.
And the cast is unnecessary and may conceal an error (forgetting to
#include <stdlib.h>). So I'd write it

Tree *new = malloc (sizeof (Tree));

and many posters to clc would write it

Tree *new = malloc (sizeof *new);

        new->val = n;
        new->left = NULL;
        new->right = NULL;
        *pRoot = new;
     }
}

main() makes successive calls to insert as in insert(&root,35); insert
(&root, 37); insert(&root, 39);
A preOrder listing as in preOrder(&root) prints correctly.

Since 39 is the last created node and the line in insert() goes
"*pRoot = new", would this not alter the variable root in main() to
point to the node that holds the last added value, viz. 39?

no. Note there are recursive calls to insert(). So the top of the tree
will always be 35. The tree constructed will be

35
\
37
\
39

Pardon me if my understanding of pointers is fuzzy,

I don't think pointers are the problem but recursion.
Try printing the tree after each insertion and you might be able see
what's going on. (I assume you fix the malloc() bug)

 

[Eric Sosman]

I was looking at this function segment that inserts a node into a
binary tree :

void insert(Tree** pRoot, int n)
{
if (*pRoot != NULL)
{
if ((*pRoot)->val > n)
insert(&((*pRoot)->left),n);
else
insert(&((*pRoot)->right),n);
}
else
{
Tree* new = (Tree *)malloc(sizeof(Tree*));

Bug here; see [*] below.

new->val = n;
new->left = NULL;
new->right = NULL;
*pRoot = new;
}
}

main() makes successive calls to insert as in insert(&root,35); insert
(&root, 37); insert(&root, 39);
A preOrder listing as in preOrder(&root) prints correctly.

Presumably, `root' in main() is set to NULL before the
first insert() call.

Since 39 is the last created node and the line in insert() goes
"*pRoot = new", would this not alter the variable root in main() to
point to the node that holds the last added value, viz. 39? Pardon me
if my understanding of pointers is fuzzy, I'd be much grateful for an
explanation showing where my understanding has got holes, obviously
I've got some way to go

You've overlooked the fact that main's insert(&root, 39)
is not the only call to insert(). Starting from the top:

1) main() calls insert(&root, 39), so insert() executes
with pRoot pointing at main's `root'.

2) insert() discovers that *pRoot is not NULL, and finds
that (*pRoot)->val is 35. 35 is not >39, so insert()
calls itself, passing &(*pRoot)->right as the first
argument. Note that this argument does not point at
main's `root' variable, but at one of the link variables
in the tree's topmost node.

3) The inner insert() discovers that *pRoot is not NULL
(remember, this is not main's `root', but a link inside
one of the tree's nodes), and finds that (*pRoot)->val
is 37. 37 is not >39, so the inner insert() calls itself
yet again, passing &(*pRoot)->right as the first argument.
This argument is a pointer to one of the link variables
in the tree's second-level node.

4) The third-level insert() now discovers that *pRoot is NULL.
It allocates memory for a new Tree[*], initializes its
elements, and then sets *pRoot to point at the new Tree.
What is *pRoot? It's the `right' link in the Tree that
the call at step (3) was working on.

You might find it helpful to draw some pictures on a bit of
paper and trace through what happens. Begin with a picture of
the entire tree as it is before the final insert() call: main's
`root' variable points to a Tree with the value 35 and a NULL
left link; the right link points to a second Tree with the value
37 and both links NULL. Now walk through the operations of the
insert(&root, 39) call, remembering that each insert() has its
very own pRoot.

[*] Unfortunately, it doesn't allocate enough memory. It
only allocates enough for a Tree*, a pointer to a Tree, and not
enough for a Tree itself. You haven't shown us exactly what a
Tree looks like, but it must be more than twice the size of a
Tree*, since it contains two Tree* plus a `val'.