Maximum Depth of Binary Tree

Problem Statement

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

The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Input: root = [1,2,3,None,None,4]
# Output: 3

Example 2:

# Input: root = []
# Output: 0

Constraints:

• 0 <= The number of nodes in the tree <= 100.
• -100 <= Node.val <= 100

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Hint 1

From the definition of binary tree’s maximum depth, can you think of a way to achieve this recursively? Maybe you should consider the max depth of the subtrees first before computing the maxdepth at the root.

Hint 2

We use the Depth First Search (DFS) algorithm to find the maximum depth of a binary tree, starting from the root. For the subtrees rooted at the left and right children of the root node, we calculate their maximum depths recursively going through left and right subtrees. We return 1 + max(leftDepth, rightDepth). Why?

Hint 3

The +1 accounts for the current node, as it contributes to the current depth in the recursion call. We pass the maximum depth from the current node’s left and right subtrees to its parent because the current maximum depth determines the longest path from the parent to a leaf node through this subtree.

Solution

Recursive DFS

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    return 1 + max(max_depth(root.left), max_depth(root.right))

Time complexity: O(n) Space complexity: O(h)

• Best Case (balanced tree): O(log(n))
• Worst Case (degenerate tree): O(n)

Where n is the number of nodes in the tree and h is the height of the tree.