Solving Maximum Depth of Binary Tree: Finding the Longest Path

The "Maximum Depth of Binary Tree" problem is focused on finding the maximum depth (or height) of a binary tree. The depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node.

Problem Statement

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

Example

Consider a binary tree:

The maximum depth of this tree is 3.

Solution Approach - Depth-First Search

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  } else {
    let leftDepth = maxDepth(root.left);
    let rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
  }
}

Breaking Down the Solution

• Recursive Approach: The solution uses a recursive depth-first search algorithm.
• Base Case: If the node is null, the depth is 0.
• Recursive Calculation: The depth of each subtree (left and right) is calculated, and the greater of the two depths is chosen, adding one to account for the current node.

Solution in Typescript one-liner

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

  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Conclusion

Determining the maximum depth of a binary tree is a fundamental problem in tree algorithms, emphasizing the use of recursion and understanding of tree traversal techniques.