CODEWITHSUNDEEP
c++binary-treebinary-search-tree
Sean Lafferty
Sean Lafferty

Reputation: 171

Calculating Height of Binary Search Tree

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;
    }
}

Upvotes: 2

Views: 15066

Answers (3)

user7367589
user7367589

Reputation: 1

Even I was facing the same problem, well the problem with your code is that in your function you are using recurssion twice and you are going to the left and right extremities, but you arent checking the possibility if the right child of one of the parent node in left subtree has its own children, hence your are not traversing to the last leaf node in your tree! hope this helps

Upvotes: 0

Andy Prowl
Andy Prowl

Reputation: 126412

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; }
}

Upvotes: 2

Synxis
Synxis

Reputation: 9388

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.

Upvotes: 10

Related Questions