Height of a tree

[Gaiety]

Hello,

i found two codes for finding out the height of the tree
(this is what creating confusion for me which one is correct)

1.
int height( BinaryTree Node t) {
if t is a null tree
return -1;
hl = height( left subtree of t);
hr = height( right subtree of t);
h = 1 + maximum of hl and hr;
return h;
}

2. int height(BST_t *root) {
if(root == NULL)
return 0;
return 1+ max( height ( root->left ), height( root->right ) );
}

for the above codes
if i have only one node in the list one function displays
height as -1 and other displays 0
(i am in confusion which one is right)
if my tree is 40 and 20 with 40 as root node
then 1 displays 1 and other displays 2.

Please can some one help me out what actually the height of the Tree is and how to find it.

[Tom Gunn]

if i have only one node in the list one function displays
height as -1 and other displays 0

Both are right. The function that returns -1 is probably treating an empty tree as an error case and returning a suitable code. The function that returns 0 is treating an empty tree as a non-error case and returning the actual height of 0 because there are no nodes.

if my tree is 40 and 20 with 40 as root node
then 1 displays 1 and other displays 2.

Both are right. The height of a BST has different technical definitions depending on who you ask. Sometimes the root is included in the count, sometimes it is not. The first function does not include the root in the height, and the second function does. Pick the one you think makes more sense and stick to it. My opinion is that the root should count if it has legit data. A dummy root should not count.

[Gaiety]

Both are right. The function that returns -1 is probably treating an empty tree as an error case and returning a suitable code. The function that returns 0 is treating an empty tree as a non-error case and returning the actual height of 0 because there are no nodes.

Both are right. The height of a BST has different technical definitions depending on who you ask. Sometimes the root is included in the count, sometimes it is not. The first function does not include the root in the height, and the second function does. Pick the one you think makes more sense and stick to it. My opinion is that the root should count if it has legit data. A dummy root should not count.

then how do we define the height of a tree?
if i want to find out a given tree is balanced or not how to find out based on height.

[Tom Gunn]

if i want to find out a given tree is balanced or not how to find out based on height.

As long as you use the same definition of height when checking the balance, either function will tell you the same thing. You can recursively check that the subtrees of each node do not differ by more than one: abs(Height(root->left) - Height(root->right)) < 2 That gives you a balance quality along the lines of an AVL self-balancing tree.