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