Find The Height of Binary Tree - Java Program

 Important points:

• Height of tree = Number of edges in longest path from root to leaf
• Height of a node = Number of edges in longest path from the node to a leaf node
• Depth of a node = Number of edges in path from root to that node

• Height of above tree is 3. Longest path is F -> B -> D -> E
• Height of Node E is 0 and depth is 3. 
• Depth of node B is 1 and height is 2. 

Pseudo Code:
FindHeight(root) {

if(root is NULL)

return -1; // return 0 if you want to count the node in the path

leftHeight <- FindHeight(root -> left)

rightHeight <- FindHeight(root -> right)

return max(lefHeight, rightHeight) + 1

}

JAVA PROGRAM:

public class BinTreeHeight {

static int max(int hl, int  hr) {

if(hl > hr) {

return hl;

}

return hr;

}

static int treeHeight(Node n) {

int hl = 0;

int hr = 0;

if(n == null) {

return -1;

}

hl =  treeHeight(n.left);

hr =  treeHeight(n.right);

return max(hl, hr) + 1;

}

    

    public static void main(String a[]) {

    Node binTree = new Node(

    new Node(null, null, 5),

    new Node(

    new Node(null, null, 6),

    new Node(null, null, 9),

    8

),

    2

);

    

    System.out.println(treeHeight(binTree));

    }

}

//OUTPUT: 3