Java Recursive code with explanation


  • -1
    C

    The maximum depth of a binary tree is defines as the number of nodes along the longest path from the root node down to the farthest leaf node. Let us take an example and try to understand what does the maximum depth means.


    In the above image we can see that the root Node (10) has two child nodes (5 and 20) and the two children have their respective sub-trees.  The maximum depth in the above binary tree is the number of nodes along the path from Node 10 to Node 16 as Node 10 is the root node and Node 6 is the farthest leaf Node which is available in the tree. Thus the depth is 5.

    Like most of binary tree problems, our approach to solve this problem will be recursive. The challenge in this problem is to find the farthest node and in the process of finding the farthest leaf node we will calculate the maximum depth. The above shown binary tree can be divided into two sub trees.

    Left Sub-Tree


    Right sub-tree

    Th maximum depth of the binary tree depends upon the maximum depth of it's two sub trees. If we find the maximum depth of the two individual sub-trees, then we can find the maximum depth of the original sub-tree by taking the maximum depth of the two sub-trees and increment it by one. The code for this algorithm is as follows:

    public int maxDepth(TreeNode root) {
        if(null==root)
            return 0;
        return 1 + (Math.max(maxDepth(root.left), maxDepth(root.right)));
    }
    

    Thanks. Happy Coding :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.