Maximum Depth of Binary Tree easy

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 1

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

Example 2

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

Steps

  1. Base Case: If the root is None (empty tree), the depth is 0.
  2. Recursive Step: Recursively calculate the maximum depth of the left and right subtrees.
  3. Maximum Depth: The maximum depth of the tree is 1 (for the root) plus the maximum of the depths of the left and right subtrees.

Explanation

The solution uses a Depth-First Search (DFS) approach, specifically a recursive post-order traversal. We start at the root. If the root is null, the depth is 0. Otherwise, we recursively calculate the depth of the left and right subtrees. The maximum depth of the entire tree is then the maximum of the left and right subtree depths plus 1 (to account for the root node). This recursive process continues until all nodes have been visited and the maximum depth is determined.

Code

# 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: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left_depth = self.maxDepth(root.left)
            right_depth = self.maxDepth(root.right)
            return max(left_depth, right_depth) + 1

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is logâ‚‚(N).