Java: Maximum Depth of Binary Tree

Thought Process

To find the maximum depth of a binary tree, we can use a recursive approach. The depth of a tree is the number of edges from the root to the deepest leaf. If the tree is empty ( root == NULL), the depth is 0. Otherwise, the depth is 1 + max(depth of left subtree, depth of right subtree). This approach ensures that we traverse the entire tree and compute the depth efficiently. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        
        if(root == null)
            return 0;

        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return 1 + Math.max(leftHeight,rightHeight);
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree(h). In the worst case (a skewed tree), the space complexity is O(n).

Code copied!