https://leetcode.com/problems/diameter-of-binary-tree/description

Understanding the Problem:

Before diving into the solution, let’s understand the problem statement. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root node.

Approach and Code Explanation:

To solve the diameter of a binary tree problem, we’ll use a recursive approach. We’ll define a helper function recurse that calculates the height of the binary tree rooted at a given node and updates the maximum diameter encountered so far.

Here’s the breakdown of the Java solution:

class Solution {
    public int maxLength = -1;
    
    public int diameterOfBinaryTree(TreeNode root) {
        recurse(root);
        return maxLength;
    }
    
    public int recurse(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = recurse(node.left);
        int right = recurse(node.right);
        maxLength = Math.max(maxLength, left + right);
        return 1 + Math.max(left, right);
    }
}

3. We define a class Solution that contains the solution logic.
4. We declare a class variable maxLength to store the maximum diameter encountered.
5. The diameterOfBinaryTree method is the entry point of our solution. It invokes the recurse method to compute the diameter of the binary tree rooted at the given root node.
6. The recurse method calculates the height of the binary tree rooted at a given node. It returns the height of the subtree rooted at the current node. Additionally, it updates the maxLength variable with the maximum diameter encountered so far.