Calculate height of a tree

Question

I am trying to calculate height of a tree. I am doint with the code written below.

#include<iostream.h>

struct tree
{
    int data;
    struct tree * left;
    struct tree * right;
};

typedef struct tree tree;

class Tree
{
private:
    int n;
    int data;
    int l,r;
public:
    tree * Root;
    Tree(int x)
    {
        n=x;
        l=0;
        r=0;
        Root=NULL;
    }
    void create();
    int height(tree * Height);

};

void Tree::create()
{
    //Creting the tree structure
} 

int Tree::height(tree * Height)
{
    if(Height->left==NULL && Height->right==NULL)
    {return 0;
    }
    else
    {
        l=height(Height->left);
        r=height(Height->right);

        if (l>r)
        {l=l+1;
        return l;
        }
        else
        {
            r=r+1;
            return r;
        }
    }
}

int main()
{
    Tree A(10);//Initializing 10 node Tree object
    A.create();//Creating a 10 node tree

    cout<<"The height of tree"<<A.height(A.Root);*/

}

It gives me corret result. But in some posts(googled page) It was suggested to Do a Postorder traversal and use this height method to calculate the Height. Any specific reason?

Answer 1

The height of the tree doesn't change with the traversal. It remains constant. It's the sequence of the nodes that change depending on the traversal.

Answer 2

But isn't a postorder traversal precisely what you are doing? Assuming left and right are both non-null, you first do height(left), then height(right), and then some processing in the current node. That's postorder traversal according to me.

But I would write it like this:

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

Edit: depending on how you define tree height, the base case (for an empty tree) should be 0 or -1.

Answer 3

Definitions from wikipedia.

Preorder (depth-first):

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

Inorder (symmetrical):

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

Postorder:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

"Visit" in the definitions means "calculate height of node". Which in your case is either zero (both left and right are null) or 1 + combined height of children.

In your implementation, the traversal order doesn't matter, it would give the same results. Cant really tell you anything more than that without a link to your source stating postorder is to prefer.

Answer 4

The code will fail in trees where at least one of the nodes has only one child:

// code snippet (space condensed for brevity)
int Tree::height(tree * Height) {
    if(Height->left==NULL && Height->right==NULL) { return 0; }
    else {
        l=height(Height->left);
        r=height(Height->right);
//...

If the tree has two nodes (the root and either a left or right child) calling the method on the root will not fulfill the first condition (at least one of the subtrees is non-empty) and it will call recursively on both children. One of them is null, but still it will dereference the null pointer to perform the if.

A correct solution is the one posted by Hans here. At any rate you have to choose what your method invariants are: either you allow calls where the argument is null and you handle that gracefully or else you require the argument to be non-null and guarantee that you do not call the method with null pointers.

The first case is safer if you do not control all entry points (the method is public as in your code) since you cannot guarantee that external code will not pass null pointers. The second solution (changing the signature to reference, and making it a member method of the tree class) could be cleaner (or not) if you can control all entry points.