Calculate Height of a Binary Tree Recursive method

user_14191742 0
Viewed 282

I want to know if this implementation is correct for finding height of BT. Please give me your thoughts on it.

public class Node {
  int value;
  Node left = null;
  Node right = null;

 public Node(int value) {
  this.value = value;
 }
}

class Main {
 public int BTHeight(Node root) {
  //tree is empty.
   if(root == null) {
     return -1;
   }
    //recur for left and right tree.
   else if(root.left != null || root.right != null) {
     return 1 + Math.max(BTHeight(root.left) + BTHeight(root.right));     
   }
    //tree has only one node. that node is both the root and the leaf
   return 0;
 }
}
binary-tree
1 Answers

No, it is not a correct implementation as your code has a compilation error here (Math.max function need two input parameters):

return 1 + Math.max(BTHeight(root.left) + BTHeight(root.right));

The definition of height as stated in the book Introduction to Algorithms, 3rd Edition (Cormen, page 1177), is:

The height of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf, and the height of a tree is the height of its root. The height of a tree is also equal to the largest depth of any node in the tree.

A NULL node it is not a tree (by definition) so there are several values of height to choose as default like undefined or -1 or 0, it depend on the purpose. The implementation of height's definition stated above is usually shorter if used -1 as height of a NULL node.

It would be like this:

public int BTHeight(Node root) {
  return root == null ? -1 : Math.max(BTHeight(root.left)+1, BTHeight(root.right)+1);}

Corner case examples:
Height of a NULL node: -1
Height of a leaf node: 0

You can use also an alternative definition:

The height of a node in a tree is the number of nodes on the longest simple downward path from the node to a leaf.

In this case it would be better to use 0 as height of a NULL node as a leaf's height is 1.

public int BTHeight(Node root) {
  return root == null ? 0 : Math.max(BTHeight(root.left)+1, BTHeight(root.right)+1);}

Corner case examples:
Height of a NULL node: 0
Height of a leaf node: 1

You can see that both codes are basically the same and that is convenient in case you have to change from one definition to another.

user_137431050
Related