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, the depth is 0.
  2. Recursive Step: Recursively calculate the maximum depth of the left and right subtrees.
  3. Max Depth: The maximum depth of the tree is 1 plus the maximum of the depths of the left and right subtrees.

Explanation

The solution uses Depth-First Search (DFS) recursively. We start at the root. If the root is null, we've reached the end of a branch and return 0. Otherwise, we recursively calculate the depth of the left and right subtrees. The maximum depth of the entire tree is one more than the maximum depth of its subtrees (because we add the current node). The Math.max() function helps us find the larger of the two subtree depths.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    } else {
        let leftDepth = maxDepth(root.left);
        let 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. We visit each node 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. In the best case (a balanced tree), H is logâ‚‚(N).