deepSWE.io

Maximum Depth of Binary Tree

TreesDFS

15 min

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

Example 1:

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

Output: 3

Recursive Solution (DFS)

The recursive approach uses a Depth-First Search (DFS) strategy to traverse the tree and find the maximum depth.

Algorithm Steps

The base case for the recursion is when a node is null, in which case we return 0.
Recursively call the function on the left and right children to get their depths.
The depth of the current node is 1 + the maximum of the depths of its left and right children.

Max Depth Found: 1

Visiting node 3 at depth 1.

Maximum Depth of Binary Tree Solution


# 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
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))