Sweaty Imposter

Maximum Depth of Binary Tree

EasyTree DFSBlind 75JuniorOpen on LeetCodeUpdated

You're 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, counting both ends. A leaf is a node with no children. A single node has depth 1 and an empty tree has depth 0. Example trees are listed row by row from the top, each row left to right, with null where a child is missing.

Examples

root = [3,9,20,null,null,15,7] returns 3

3920157
One longest path: 3, 20, 15.

The longest root-to-leaf paths are 3, 20, 15 and 3, 20, 7, each with 3 nodes. The path 3, 9 ends at the leaf 9 after only 2 nodes.

root = [1,null,2] returns 2

12

The root 1 has only a right child 2, so the one root-to-leaf path is 1, 2, with 2 nodes.

Constraints

  • 0 <= number of nodes <= 10^4

Hints

Hint 1

How does the depth at a node relate to the depths of its children?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Recurse: an empty subtree has depth 0, and any other node has depth 1 plus the larger of its two subtree depths. Each call finishes only after both children return, so the answer builds up from the leaves to the root. O(n) time since every node is visited once, and O(h) space for the call stack, where h is the tree height (up to n for a tree shaped like a chain).

Time

O(n)

Space

O(h)

Pitfall

Counting edges instead of nodes, which returns 2 instead of 3 for the first example. Return 0 for a null node, not -1, so a single node has depth 1.

Solutions

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