CODEWITHSUNDEEP
c++data-structuresbinary-tree
nym_kalahi
nym_kalahi

Reputation: 91

Binary Tree Height Function

I'm working on a function to find the height of a binary search tree. I found a method that seems like it should work, but I keep getting this error, and I don't know whats wrong with it: Unhandled exception at 0x00903417 in PA5.exe: 0xC0000005: Access violation reading location 0x00000004.

Here are my height functions...

template <class T>
int BST<T>::height()
{

    return displayHeight(mRootNode);    

}

template <class T>
int BST<T>::displayHeight(BST<T> *node)
{
    if (node = NULL)
    {
        return 0;
    }

    int left = displayHeight(node->mLeft);
    int right = displayHeight(node->mRight); 

    if (left > right)
        return 1 + left;
    else
        return 1 + right;
}

This is the implementation in the main function...

 cout << endl << "height: " << tree.height();

If I should include anything else, let me know. Thanks!

Upvotes: 4

Views: 15101

Answers (4)

Ashit
Ashit

Reputation: 59

This is because you've assigned the node to NULL i.e NULL value is 0 , so condition fails.

do if(node==NULL) instead of if(node=NULL)

Upvotes: 0

BlackDragon
BlackDragon

Reputation: 31

Method to find the height while creating a tree(BST):For both left subtree and right subtree::

Put the elements you want to put in your binary tree in an array before you create the actual tree. Calculate the number of elements which are greater than the root, which will be going to the left of the tree and similarly with the right side.

Then while you add the elements to your tree. Everytime set a flag bit to 1 or 0 depending on whether you are adding it to the left subtree or the right.

if(root->right && flagleft==1)
     no_left--;
     else if(root->right && flagright==1)
         no_right--;

This is while you append a node to the left side.

if(root->left && flagl==1)
nl--;
else if(root->left && flagr==1)
nr--;

This is while you append a node to the right side.

Upvotes: 1

codaddict
codaddict

Reputation: 455440

if (node = NULL)

should be

if (node == NULL)

because in C++ = is an assignment operator and == is the relational operator for comparison.

Why the crash?

When you do if (node = NULL), you are assigning NULL to node and since NULL is 0 the if condition fails. So you go ahead and call the function recursively on the nodes's children. Now suppose node was actually NULL when the function was called for the first time, you'll be doing the recursive calls on NULL's left and right children!!! Leading to crash.

Upvotes: 7

Jake H
Jake H

Reputation: 1740

You are assigning null to your node parameter variable in your if statement. 

if (node = NULL)
{
    return 0;
}

should be 

if(node == NULL) ...

Upvotes: 1

Related Questions