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 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 recursive approach. The function MaxDepth checks if the root is null. If it is, it returns 0. Otherwise, it recursively calls itself on the left and right subtrees to find their maximum depths. The maximum depth of the entire tree is then the maximum of the left and right subtree depths plus 1 (to account for the current node).

This recursive approach elegantly explores all possible paths from the root to the leaves, ensuring that the longest path is identified. The recursion naturally unwinds, providing the maximum depth at the end.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftDepth = MaxDepth(root.left);
            int rightDepth = MaxDepth(root.right);
            return Math.Max(leftDepth, rightDepth) + 1;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), H is log₂(N), resulting in O(log N) space complexity.