Basic question in binary tree node insertion

Discussion in 'C Programming' started by Indrajeet, Oct 11, 2009.

  1. Indrajeet

    Indrajeet Guest

    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 :)
     
    Indrajeet, Oct 11, 2009
    #1
    1. Advertising

  2. On 11 Oct, 19:13, Indrajeet <> wrote:

    > 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)

    > 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, Oct 11, 2009
    #2
    1. Advertising

  3. Indrajeet

    Eric Sosman Guest

    Indrajeet wrote:
    >
    > 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'.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Oct 11, 2009
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,470
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,136
  3. Tjerk Wolterink
    Replies:
    2
    Views:
    1,440
    Dimitre Novatchev
    Aug 24, 2006
  4. Peter Mueller
    Replies:
    6
    Views:
    4,576
    Stefan Ram
    Jan 13, 2008
  5. John Bankhead

    Null parent node on custom tree node after populate on demand

    John Bankhead, Dec 4, 2006, in forum: ASP .Net Web Controls
    Replies:
    0
    Views:
    285
    John Bankhead
    Dec 4, 2006
Loading...

Share This Page