Tree: Height of a Binary Tree Hackerrank

The height of a binary tree is the number of edges between the tree’s root and its furthest leaf. This means that a tree containing a single node has a height of 0.

Complete the getHeight function provided in your editor so that it returns the height of a binary tree. This function has a parameter, root, which is a pointer to the root node of a binary tree.

Input Format

You do not need to read any input from stdin. Our grader will pass the root node of a binary tree to your getHeight function.

Output Format

Your function should return a single integer denoting the height of the binary tree.

Sample Input

Note: A binary search tree is a binary tree in which the value of each parent node’s left child is less than the value the parent node, and the value of the parent node is less than the value of its right child.

Sample Output

3
Explanation

The longest root-to-leaf path is shown below:

There are 4 nodes in this path that are connected by 3 edges, meaning our binary tree’s height=3. Thus, we print 3 as our answer.

Solution

We are using the following basic recursive algorithm for calculating the height of a binary tree:
if t is empty,
getHeight(t) = -1
else
getHeight(t) = 1 + MAX( getHeight( leftSubtree(t), rightSubtree(t) ) )

/*The tree node has data, left child and right child 
struct node
{
    int data;
    node* left;
    node* right;
};

*/
int height(node * root)
{
     if (root == NULL)
  return -1;
return max(height(root->left),height(root->right))+1;

}
  

Java
public static int getHeight(Node root){
    if (root == null){
        return -1;
    }
    else{
        return 1 + Math.max( getHeight(root.left), getHeight(root.right) );
    }
}
JavaScript
if( root === null ){
    return -1;
}
else{
    return 1 + Math.max( this.getHeight(root.left), this.getHeight(root.right) );
}
PHP
    public function getHeight($root){
        if($root == null) {
            return -1;
        }
        
        return 1 + max($this->getHeight($root->left), $this->getHeight($root->right));
    }
Python
    def getHeight(self, root):
        if root == None:
            return -1
        else:
            return 1 + max( self.getHeight(root.left), self.getHeight(root.right) )

int getHeight(Node* root){
    if ( root == NULL ){
        return -1;
    }
    else{
        return 1 + max( getHeight(root->left), getHeight(root->right) );
    }
}