General Trees, calculating height

Ok, I've been trying this over and over and I can't seem to get it right. I have a general tree, and I just need to calculate the height of the tree. This is what I have so far:

Code:

---

//Is a member function of my general tree class
                int getHeight(gNode *rt)
                {
                        if (rt == NULL) return 0; //if given node is null, return 0
                        if (rt->isLeaf()) return 1; //if given node is a leaf, return 1
                        int height = 0; //height starts at 0
                        if (rt->getSib() != NULL) //if node has a sibling
                                height = getHeight(rt->getSib()); //set height as height of sibling
                        if (!rt->isLeaf())  //if node is not a leaf
                                height += getHeight(rt->getChild()); //height += height of child

                        return height;
                }

---

All I can say is that the answers I get are close. I know I'm missing something, but I don't know what it is, any ideas?

this is my feeble attempt - it may be WAY off
this is a assuming that child != child->sibling->sibling

Code:

---

int getHeight(gNode *rt)
{
       
        if(!rt)     
                return 0;   
        //recursive stopper
        if(rt->isLeaf())
                return 1;

        int path1, path2;
        path1 = path2 = 0;

        //i'm assuming there much be a child to have a sibling
        if(rt->getChild())
        {
                //find out how long the path is straight down through all the children
                path1 = getHeight(rt->getChild());

                //if siblings - find the longest path thru them
                //this should visit all the siblings and the children
                //..children first.
                if(rt->getSib())
                        path2 = getHeight(rt->getSib()) - 1;
                  //we subtract 1 because we are making a 'horizontal' move, but the design
                // of this function will add 1 to the return value automatically. subtracting
                //one offsets this
                //edit: by 'horizontal' i'm assuming each child make the
                ///tree grow taller (downward), and that each sibling
                //makes it grow wider (from a child)

        }

        //the height is the longest path from the root to a leaf
        //path 1 is the longest path of the children
        //path 2 is is the longest path of a mixture of children and siblings
        //return the largest of the 2 paths plus one (this node)

        //if path 1 and 2 are the same, save yourself a few CPU cycles
        //and return it automatically       
        if(path1 >= path2)
                return (path1 + 1);
        else
                return (path2 + 1);
               
}

---

edit: btw - i read somewhere that NULL is not officialy part of c++ and that NULL should not be used in c++. even for pointers. but i can't remember where i read this, so i guess it's up to you

There are some good tree tutorials in Prelude's Corner of the FAQ. You may want to give them a read.

Quzah.

Why are you settting the node height to the height of the sibling and then adding the height of the node? IF a node and its siblings are all on the same level tt seems to me you want to be returning the maximum value between all of the siblings with the height being calculated as child's height + 1.