Maximum Depth of Binary Tree - Java Solution

1. Introduction

In this post, we'll explore a fundamental problem in binary tree algorithms: finding the maximum depth of a binary tree. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Understanding tree depth is crucial for many applications in computer science, from data organization to algorithm optimization.

Problem

Given the root of a binary tree, the goal is to determine its maximum depth, which is the length of the longest path from the root to the most distant leaf node.

2. Solution Steps

1. Use a recursive approach to traverse the tree.

2. At each node, calculate the depth by adding 1 to the maximum depth of its left and right subtrees.

3. If a node is null, return 0, indicating no depth.

4. The depth of the root node is the maximum depth of the tree.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class MaximumDepthBinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(maxDepth(root)); // Test the function
    }

    // Function to find the maximum depth of a binary tree
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Output:

3

Explanation:

1. maxDepth: This function computes the maximum depth of a binary tree using recursion.

2. For each node, it checks if the node is null. If so, it returns 0, indicating that there is no depth.

3. It then calculates the maximum depth by taking the maximum of the depths of the left and right subtrees and adding 1 for the current node.

4. This recursive approach ensures that the depth of each subtree is fully explored, and the maximum depth is correctly calculated.

5. The function returns the depth of the tree, which is the length of the longest path from the root to a leaf.