Binary Tree Function : TreeFindRoot. Where's the mistake?

Good morning ladies and gentlemen,
this is so far my first post. The time is around 6 am in my country and you are really my last hope, as at the moment I have run out of ideas and coffee :p, and everything seems mumbo jumbo to me. So, let's get to the point.
My source of frustration is a function I implemented to use for my binary search tree. A doubly linked binary tree like this:

Code:

---

typedef struct treenodeT treenodeT;
struct treenodeT
{
        int id;
        docnodeT *head;        /* this doesn't matter at the moment */
        struct treenodeT *parent;
        struct treenodeT *left;
        struct treenodeT *right;
};

---

where the root differs from the other treenodes as its parent is set to NULL. So, I have implemented around a dozen or more functions in order to make this binary tree functional, such as functions to insert/remove/search for a node etc! One of them that's been used thoroughly by the others is a function which returns the root of the tree (if any), given a pointer at a random treenode. This is it:

Code:

---

treenodeT *TreeFindRoot(treenodeT *treenodeP)
{
  treenodeT *root;
  treenodeT *hold;
  root = treenodeP;
  if (root == NULL)  return NULL;
  else
  {
        if (root->parent == NULL) return root;
        else
        {
          hold = root->parent;
          while (hold != NULL)
          {
                root = hold;
                hold = hold->parent;
          }
          return root;
        }
  }
}

---

This function seems to work correctly most of the times called, but other times, according to the GNU debugger (which i wish to knew how to make full use of), it stucks in an endless loop when it reaches the line:

Code:

---

while (hold != NULL)

---

I have read and reread and rewritten this function 100 times with all the possible loops, and still, its getting stuck at the same point when running the program. :confused: Any ideas? Does anybody see what I cannot? Please?

Thanks in advance, especially for your patience :)
E.

It probably means your tree is broken.

A good place to look might be say where you deleted a node, and forgot to update the parent of the promoted children of the node.

An extremely common thing about rookie programmers is that they see special cases where there aren't special cases. First look at your inner if-statement and ask yourself "Does this code end up doing the same thing whether the if-statement expression is true or false?". In this case, the answer is yes.
Here's a simplified version:

Code:

---

treenodeT *TreeFindRoot(treenodeT *treenodeP)
{
    if (treenodeP != NULL)
        while (treenodeP->parent != NULL)
            treenodeP = treenodeP->parent;

    return treenodeP;
}

---

Granted the initial test for NULL may be necessary, but then again it may actually not be necessary. For where you likely use this function from, I would expect that it is probably okay to just make the initial if-statement into an assert instead.

Less code == less bugs.

Having said that though, I agree with Salem, the bug is not in this function, the bug is that your data structure is corrupt, probably due to insert/remove function bugs. See if you can simplify the logic of those functions until you can see the problem.

Actually, you are right both of you! I found the bug in my huuuuuuuge TreeRemove function which i rewrote completely from scratch! (/crying)...
I could post the final version, in case there's anybody wondering, I really doupt it though :p

Thank you for the help, the advice and the quick answers!:cool:

Good evening again, ladies and gentlemen!
I hope you are all doing well, your health to be the best, your wallet full of money and your love life better than ever! Also I wish you to be in a good shape to spot mistakes because tonight I'm gonna 'bug' you again and kindly ask for your help! :rolleyes:

So, let's say we have a network. Every node of the network is a treenode of the Binary Search Tree above. We can add and remove network nodes. But!
Nodes can also store files, and every node holds a pointer to the head of a singly linked list of files (that's the docnode I mentioned previously). Supposing that we have 3 nodes with ids 5, 9, 12, (no files yet) if i want to store the file with file_id=9, i should put it in the node 9. For file with file_id=10, the corresponding treenode is the node 12. The file with file_id=1 will go to node 5. And finally (this point is very important), the file with file_id=20 will be stored to node 5, too.
To make th elong story short, that means: every file with file_id > node_max_id will be stored to the node with the minimum id instead.

At the same time, if i want to add a new treenode at my network, let's say with id = 25, Then the file with file_id=20 must be moved to node 25. And guess what: If i want to remove a node from the network, I must firstly put the files store there to another node that completes the criteria ...

So, let's say that my list is a structure like this:

Code:

---

typedef struct docnodeT docnodeT;
struct docnodeT
{
  int id;                               
  int type;                                /* Available types 1, 2, 3 */
  docnodeT *next;                /* Used to point to next node */
};

---

and the files such a list holds are presorted.
Then I 've written some functions to add/remove/search a node in the list etc, and two special functions:

The first funcion gets as an argument an initial list of this kind, splits the list in two, comparing the files to a given key, and returns the part that contains all files with file_id less or equal to the key, while the initial list must contain only the rest of files (if any).

Code:

---

docnodeT *DocListSplit(docnodeT *oldlist, int key)
{
  docnodeT *newlist = NULL;
  docnodeT *index;
  docnodeT *hold;

  /* Nothing to split so far */
  if (oldlist == NULL) return newlist;
  /* All the files have already file_id > key, so no need to move them */
  if (oldlist->id > key) return newlist;

  /* If I reached this point, it means that there are files to move! */
  newlist = oldlist; /* At least the first file of oldhead belongs to newhead */
  index = oldlist;

  while (( index != NULL ) && (index->id <= key))
  {
        hold = index;                  /* This var will hold the last file of our newlist */
        index = index->next; /* This var will hold the first file of our old list */
  }
  hold->next = NULL;          /* The last file of our new list must point to NULL */
  oldlist = index;                  /* if this var is NULL, means that all files moves to newlist */
  return newlist;
}

---

The second function gets as arguments to lists, headto and headfrom. What it does is to move all the contents of headfrom to headto, and return headto. And this is exactly how it does it:

Code:

---

docnodeT *DocListMerge(docnodeT *listto, docnodeT *listfrom)
{
  docnodeT *newlist;
  docnodeT *indexfrom;               
  docnodeT *indexto;
  docnodeT *newlistindex;

  /* Whatever there is in listto, there is nothing to be merged with */
  if (listfrom == NULL) return listto;
  if (listto == NULL)                /* The destination list is empty, */
  {
        newlist = listfrom;
        listto = newlist;                /* we 'exchange' it with the source list, */
        listfrom = NULL;                /* then make the source list point to NULL. */
        return listto;
  }
 
  /* If we reach this point, it means that both lists have at list an item */
  /* Now we need to add all the files in one list, but in the correct order */
  /* The destination list must begin with the file with the smallest id */

  if (listto->id < listfrom->id)
  {
        newlist = listto;
        indexto = listto->next;  /* indexto will point us to the first unused file of listto */
        indexfrom = listfrom;        /* indexfrom will point us to the first unused file of listfrom */
  }
  else if (listfrom->id < listto->id)
  {
        newlist = listfrom;
        indexto = listto;
        indexfrom = listfrom->next;
  }

  newlistindex = newlist;        /* This index will always point us to the last file of the newlist */

  /* Now we have to check simultaneously both of our indexes for the next file */
  while ((indexto != NULL) && (indexfrom != NULL))       
  {                                                                                                       
        assert(indexto->id != indexfrom->id);               
        /* at this point the world explodes and green monkeys take over the planet */       
        if (indexto->id < indexfrom->id)
        {
          newlistindex->next = indexto;
          indexto = indexto->next;
          newlistindex = newlistindex->next;
        }
        else if (indexfrom->id < indexto->id)
        {
          newlistindex->next = indexfrom;
          indexfrom = indexfrom->next;
          newlistindex = newlistindex->next;
        }       
  }
 
  /* If we reach this point, it means that one of indexto,indexfrom is NULL */
  /* We find it and then continue adding files from the other one */
  /* These indexes can't be NULL simultaneously */
  if (indexfrom == NULL)
  {
        assert (indexto != NULL);
        while (indexto != NULL)
        {
          newlistindex = indexto;
          indexto = indexto->next;
          newlistindex = newlistindex->next;
        }
  }
  else if (indexto == NULL)
  {
        assert (indexfrom != NULL);
        while (indexfrom != NULL)
        {
          newlistindex->next = indexfrom;
          indexfrom = indexfrom->next;
          newlistindex = newlistindex->next;
        }
  }

  /* at this point, both our indexto, indexfrom must be NULL */
  assert (indexto == NULL);
  assert (indexfrom == NULL);

  /* now we re setting our last node of the destination list to be NULL */
  newlistindex->next = NULL;

  listto = newlist;      /* Source1 list is set to be the Destination list */
  listfrom = NULL;        /* and source2 list is set to NULL */
  return listto;
}

---

I'm gonna right down the functions I use when I join a new node to the network! That will be sometime in the near future, but in the meanwhile, does anyone see something which is not quite obvious to me?

Thank you again in advance not only for your will to help,
oh great Gods and Godesses of programming, (ok enough ..kissing for today!:p)
but also for your patience, if you manage to read it all!
E.

> oldlist = index; /* if this var is NULL, means that all files moves to newlist */
This WON'T change the value of the parameter you passed in the caller.
Since you seem to be trying to return two results from this function.

docnodeT *DocListSplit(docnodeT *oldlist, int key, docnodeT **remainder)
...
*remainder = index;

Ehm thank you! I'm not quite sure I understand what I have to change so far... but!
I think you suggest me something like this ?

Code:

---

docnodeT *DocListMerge(docnodeT *listto, docnodeT **listfrom);
docnodeT *DocListSplit(docnodeT *newlist, int key, docnodeT **oldlist);

---

I am a little confused if I have to do this for both functions as long as they return the new (or transformed) list, but they need the other one to be changed as well...
Whatever I'm gonna give it a try! Thank you