algoadvance

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

Clarifying Questions

  1. What should be returned if the binary tree is empty?
    • If the input binary tree root is None, the output should be 0 because there are no nodes in the tree.
  2. How are leaf nodes represented in the input tree?
    • Leaf nodes are represented with their left and right children being None.

Strategy

The strategy to find the maximum depth of a binary tree is to use Depth-First Search (DFS). This can be implemented either iteratively or recursively. Each time we descend one level in the tree, we should account for the depth.

We’ll use a recursive approach for simplicity:

  1. If the current node is None, return 0 since it doesn’t contribute to the depth.
  2. Recursively calculate the maximum depth of the left and right subtrees.
  3. The maximum depth at the current node will be 1 + max(left_depth, right_depth) where left_depth and right_depth are the maximum depths of the left and right subtrees respectively.

Code

Here is the Python code for the problem:

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

Time Complexity

The time complexity is (O(n)), where (n) is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space Complexity

The space complexity is (O(h)), where (h) is the height of the tree. This is due to the recursion stack. In the worst case (completely unbalanced tree), the height will be (O(n)). In the best case (completely balanced tree), the height will be (O(\log n)).

Try our interview co-pilot at AlgoAdvance.com