Maximum Depth of Binary Tree: Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].
• -100 <= Node.val <= 100

Try this Problem on your own or check similar problems:

1. Balanced Binary Tree
2. Maximum Depth of N-ary Tree
3. Time Needed to Inform All Employees

Solution:

public int maxDepth(TreeNode root) {
    if(root == null) return 0;

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

Explanation:

Remember how we used BFS for the shortest path to leaf node (min depth) in Minimum Depth of Binary Tree , well in this case the we can use DFS since by the problem statement we have to find the longest root-to-leaf path so the optimization we did with BFS is not useful for this problem. The problem is trivial we check left and right subtree depth and have a base case for root == null to start iterating back from the recursion stack, we just return the deeper subtree.