šŸ”— LeetCode

Maximum Depth of Binary Tree

EasydfsAmazonMicrosoft

Given the root of a binary tree, return its maximum depth.

Examples

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

Constraints

    šŸ’” Hints

    Hint 1

    A binary tree depth is the maximum of left and right depths + 1.

    Algorithm Complexity

    Official asymptotic Big-O runtime and auxiliary memory analysis

    Linear
    Algorithmic Approach

    DFS to find depth.

    Time ComplexityO(N)
    Why:

    Depth-First Search (DFS) visits every node in the binary tree exactly once to evaluate max depth.

    Space ComplexityO(H)
    Why:

    The recursion call stack depth equals the height of the tree H (O(log N) average, O(N) worst-case skewed).

    Big-O Growth CurveLinear (O(N))
    Execution time scales directly in proportion to the input size.

    šŸ” Dry Run

    Solutionā± O(N) | šŸ’¾ O(H)
    root
    3
    9
    20
    15
    7