Maximum Depth of Binary Tree easy

Problem Statement

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

Steps

  1. Base Case: If the root is null (empty tree), the maximum depth is 0.
  2. Recursive Step: Recursively calculate the maximum depth of the left and right subtrees.
  3. Maximum Depth: The maximum depth of the entire tree is 1 (for the root) plus the maximum of the depths of the left and right subtrees.

Explanation

The solution uses a depth-first search (DFS) approach, specifically a post-order traversal. We recursively explore the tree. For each node, we find the maximum depth of its left and right subtrees. The depth of the current node is then one more than the maximum depth of its children. The recursion continues until we reach leaf nodes (nodes with no children), which have a depth of 1. The function then propagates the maximum depth back up the tree until it reaches the root.

Code

/**
 * 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; // Base case: empty tree has depth 0
        } else {
            int leftDepth = maxDepth(root.left); // Depth of left subtree
            int rightDepth = maxDepth(root.right); // Depth of right subtree
            return Math.max(leftDepth, rightDepth) + 1; // Max depth of subtree + 1 for the current node
        }
    }
}

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(H) in the worst case, where H is the height of the tree. This space is used for the call stack during the recursive calls. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is logâ‚‚(N).