Maximum Depth Of Binary Tree#

Problem#

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

Example#

The tree with root 3, children 9 and 20, where 20 has children 15 and 7, has depth 3. An empty tree has depth 0.

Optimal approach#

The depth of any tree is one (for the current node) plus the greater of the depths of its two subtrees. Recurse into the left and right children, take the larger result, and add one. A null node contributes a depth of 0, which is the base case. This depth-first solution visits every node once.

You can also solve it with a breadth-first level-order traversal, counting the number of levels; the recursion below is shorter and just as efficient.

Solution#

 1class TreeNode:
 2    def __init__(self, val=0, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6
 7
 8def max_depth(root: TreeNode | None) -> int:
 9    if root is None:
10        return 0
11    return 1 + max(max_depth(root.left), max_depth(root.right))
12
13
14root = TreeNode(3, TreeNode(9),
15                   TreeNode(20, TreeNode(15), TreeNode(7)))
16print(max_depth(root))  # 3
17print(max_depth(None))  # 0

Complexity#

• Time: O(n), one visit per node.
• Space: O(h) for the recursion stack, where h is the height.

More at the trees topic. Keep going with the 60-day challenge.