Calculating Height of Binary Search Tree

Question

I've been searching for how to calculate the height of a Binary Search Tree and my research has lead me to the following implementation. I'm still trying to wrap my head around why it should work, but I'm also unsure why it isn't working. Here is my height function.

int BinaryTreeNode::height() const {
    int lefth = left->height();
    int righth = right->height();
    if(lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

and here's my class definition for the node

class BinaryTreeNode {
  public:
    Data * nodeData;
    BinaryTreeNode * left;
    BinaryTreeNode * right;

When I try to run it my program locksup and crashes. Am I missing something obvious?

EDIT: Why shouldn't this work?

int BinaryTreeNode::height() const {
    int l = 0;
    if (left != NULL) {
        left->height();
    }
    int r = 0;
    if (right != NULL) {
        right->height();
    }
    if (l > r) {
        return l + 1;
    }
    else {
        return r + 1;
    }
}

Solution 1

Your tree is not infinite. So, I suppose some nodes do not have left or right childs, and the pointers left and/or right are null in this case. You have to check for their existence before trying to use them.

Try that function instead:

int BinaryTreeNode::height()
{
    int l = left ? left->height() : 0;  // height of left child, if any
    int r = right ? right->height() : 0; // idem for right child
    return 1 + max(l, r);
}

Note: I have simplified your computations of height.

Solution 2

The problem is that your function never checks if the child pointers are NULL, so apart from dereferencing an invalid pointer, you have a recursive function that misses a base case:

Try this version:

int BinaryTreeNode::height() const 
{
    int lefth = 0;
    if (left != NULL) { lefth = left->height(); }

    int righth = 0;
    if (righth != NULL) { righth = right->height(); }

    if (lefth > righth) { return lefth + 1; } 
    else { return righth + 1; }
}

Comments

[Synxis]

You forgot to assign the value of left->height() to lefth (and same for right child) ;)

[Sean Lafferty]

Your code works but I tried rewriting it like but it doesn't. What did I break? (put the code in OP)

[Andy Prowl]

@SeanLafferty: What you pasted is the original version of my code, which indeed was broken (I forgot the assignment). Now it works. But I admit this version by Synxis is better

[Andy Prowl]

@SeanLafferty: Btw, the OP is you (Original Poster), not the question.

[Sean Lafferty]

The function returns a height of 1 with my updated code, but yours correctly outputs 4 (which is the height). I thought our code would do the same thing but maybe max() does something I didn't account for in my rudimentary version?

[Andy Prowl]

@SeanLafferty: Again, that is because the version you posted lacks the assignments.

[Andy Prowl]

@SeanLafferty: Should be l = left->height(); instead of just left->height();, same for right. That was a mistake of mine, sorry for that

[Synxis]

@Sean I agree with Andy, the version you posted is his original one, which was missing the assignment. Try mine, or his new one, for example.

[Sean Lafferty]

Thanks I have it working now. I'm still a little shaky on how it works though, like aren't r and l both 0 before it gets to the max operation where it adds the 1 to either or?

[Synxis]

The ternary operator recursively calls height() if the child exists, and assign the result to the variable, or assign 0 to it (height of non-existent child is 0). So, l and r are the heights of repectively the left and right child. Then the height of the node is 1 + the maximum height between left and right. See ternary operator.

[Jim Balter]

@SeanLafferty If you have absolutely no idea how to read C code, just say so.