4. Maximum Depth of Binary Tree

EasyTree Binary Tree DFS

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf.

Example 1

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

Example 2

Input: root = [1,null,2]
Output: 2

Constraints

The number of nodes is in the range [0, 10^4]
-100 <= Node.val <= 100

💡 Hint 1

The depth of a tree is 1 + the larger depth of its two subtrees.

💡 Hint 2

An empty tree has depth 0.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Recursive DFS: an empty node has depth 0; otherwise the depth is 1 + max(depth(left), depth(right)). An iterative BFS that counts levels works equally well and avoids deep recursion on skewed trees.

Time O(n)Space O(h), where h is the tree height

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {number}
 */
function maxDepth(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit