Coding Interview Questions | Maximum Depth

January 3rd, 2024

Maximum Depth Problem Introduction:

This summary will talk about my solution to the maximum depth problem as seen on leetcode here.

How do you solve the Maximum Depth Problem in O(h) time?

Solution:

function maxDepth(root: TreeNode | null): number {
  if (!root) {
    return 0;
  }

  const leftHeight = maxDepth(root.left);
  const rightHeight = maxDepth(root.right);

  return Math.max(leftHeight, rightHeight) + 1;
}

Maximum Depth Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Base Case Handling:

   • The algorithm starts by checking if the current node (root) is null, which indicates the end of a branch. In this case, it returns 0, contributing to the depth calculation.

2. Recursive Depth Calculation:

   • The algorithm recursively calculates the depth of the left and right subtrees using calls to maxDepth(root.left) and maxDepth(root.right).

3. Maximum Depth Determination:

   • The Math.max(leftHeight, rightHeight) + 1 expression determines the maximum depth between the left and right subtrees. Adding 1 accounts for the current node in the depth calculation.

Complexities

1. Time Complexity: The time complexity of the solution is O(h), where h is the height of the binary tree.
2. Space Complexity: Similarly, the space complexity of the solution is O(h) as up to h function calls are added to the stack during the traversal of the binary tree.