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?

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

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.

View more solutions

Comments

[Sandeep]

so do you think if i change the order, first right tree hiegnt and then left tree height(recursive) the result will be different?

[Mizipzor]

@Sandeep: Changing the order doesn't change the result. Changing the definition of height of an empty node will.

[Hans W]

Sandeep: Doing the right tree first and then left would still be post-order. Post-order means you process the current node after (post) you process the children. In this case, post-order is the only alternative as it would be impossible to determine the height as seen from a node without looking at the heights of the children first. See en.wikipedia.org/wiki/Tree_traversal if you feel unsecure about tree traversal orders.

[Mizipzor]

I cant see any specific reason for using such a postorder traversal. Maybe the user just considers postorder the default if youre unsure? Or he felt that "do a traversal" was to vague?

[Sandeep]

Thanks Hans...In all the documents I always got Traverse the left subtree. Traverse the right subtree. Visit the root. So I always had in back of my mind that left is traversed before right but otherwise is also true. I am clear now as the only requirement for postorder is that child is traversed after children(left right order doesnt matter)

[Admin]

I upvoted, but in my opinion, a recursive traversal may be interpreted as either pre-order or post-order (it depends where the current-node work is done), but since your function does some work both before and after the recursive calls, it is something else. I think of these things as XML-order traversals.

[Hans W]

Steve314: What work does my function do before the recursive calls?

[Admin]

@Hans - it checks whether it's at an actual node, or whether you just recursed down a null pointer. It's debatable whether this is really traversing the maybe-node, I suppose, since it's only looking at the pointer, not at what it points to, but to me the entry into the recursive call is the step down into the next node, and any code prior to the nested calls is therefore traversal of that node. If I'm feeling really pedantic, I'll even include reading the pointers to the child nodes, which obviously has to be done first in order to pass them as parameters to the nested calls.

[Hans W]

Steve314: I find it hard to imagine what code would have to look like to qualify as post-order traversal by your standards.

[Admin]

@Hans - when I think in terms of traversal I'm usually using some kind of iterator class, so the node is "traversed" when the "next" method exits, leaving the state referring to the node. It's basically the separation of abstractions in the visitor pattern. With a simple recursive traversal, the separation isn't there, though I guess the truth is that I'm a bit wierd.

[Sandeep]

David. I tested with 3 4 5 6 7 and it gave result as 4. Where do you see problem.

[David Rodríguez - dribeas]

Assume that you have two nodes, Root and one to the right. You call height in Root, as right is not null it enters the else branch, that will call l=height(Height->left);. That recursive call receives a null pointer and tries to dereference it in the if to check whether Height->left is null. Dereferencing a null pointer (Height in the recursive call is null) yields undefined behavior and in most cases the application death.

[Rasmi Ranjan Nayak]

If I change the code a little int Tree::height(tree *node) { if (!node) return 0; return max(height(node->left), height(node->right)); }. Why does it work. Why it returns Zero