Maximum Depth of Binary Tree

Problem Statement

LeetCode-104: 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.

Approach

The problem can be solved using a recursive approach. The maximum depth of a binary tree is the maximum of the maximum depth of its left and right subtrees plus one.

Implementation

Following is the implementation of the above approach.

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

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

Complexity Analysis

The time complexity for the above approach is $O(n)$ where $n$ is the number of nodes in the binary tree. The space complexity is $O(h)$ - for recursive stack, where $h$ is the height of the binary tree.