Maximum Depth of Binary Tree

This article is originally written at Vishy tech notes

Problem Statement: We have to find the maximum depth of the Binary Tree.

Maximum depth can be defined at the maximum number of nodes at the longest path to the deepest leaf node.

Consider the Input as : [3,9,20,null,null,15,7]

In the above input,

3 is root node value, it has two childs left is 9 and right is 20;
Again the node with value 9 has no child nodes which is written as null and null (means no child with value or no node).
And the node with value 20 has two child nodes which has child nodes 15 and 7.

Fromt the above example we can understand the path 3 -> 20 -> 7 is largest. So the maxiumum depth in this example is 3.

Pseudo Code

• Check whether the node is null or not. If it is null then return the height as 0. If not continue.
• Check wehther there are any child nodes. If no child nodes then return the height as 1.
• If there are any one child node, then we have to find the height of those child nodes recursively.
• Find the height of left node, it can be done by invoking the same method with the left node passed.
• Second find the height of left node, it can be done by invoking the same method with the right node passed.
• Both the left node and right node will be going till both their children are null.
• Once we get both the height of left and right node, we will whichever is maximum height and then we will add current node depth (+1) and then return.

Java Code

private static int findHeight(TreeNode node){
    if(node!= null && node.left == null && node.right == null){
        return 1;
    }else if( node != null && (node.left != null || node.right != null)) {
        int leftHT = findHeight(node.left);
        int rightHT = findHeight(node.right);
        return Math.max(leftHT, rightHT)+1;
   }
   return 0;
}