Diameter of Binary Tree

Problem Statement

The problem is straightforward if you understand the structure and properties of a binary tree. You are provided with the root node of a binary tree and must compute the diameter of this tree. The diameter is defined as the length of the longest path between any two nodes within the tree. This path can either pass through the root or not. Critically, what truly marks the diameter is the count of edges in the longest possible path that can be found from one node to another across the tree. This measurement does not take node values into account but purely the structure and connections within the tree.

Examples

Example 1

Input:

root = [1,2,3,4,5]

Output:

3

Explanation:

3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2

Input:

root = [1,2]

Output:

1

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

Approach and Intuition

To solve the problem, we need to focus on understanding the measurements and the properties of tree traversal:

1. Maximum Depth Calculation:

   • Each time we visit a node, we'll consider the length of the paths to its left and right child nodes.
   • The idea revolves around calculating the depth from each node downwards and simultaneously keeping track of the maximum diameter encountered.

2. Recurrence and Helper Functions:

   • Typically, a helper function calculates the depth from the node downward — summing edges to get to the furthest leaf node.
   • For each node visited, the potential diameter considering that node as the highest ancestor is the sum of the depths of the left and right subtrees.

3. Update Global Diameter:

   • As we calculate the depth for each node, update a global variable that keeps track of the maximum diameter found so far.
   • This diameter will be the sum of the maximum depths reached in the left and right subtrees rooted at the current ancestor node.

4. Result from Recursion:

   • A recursive approach works well here, as we need to traverse the tree and at every node, simultaneously calculate the depth for subtree and potentially update the diameter.

5. Edge Case:

   • When the tree is very small (1 or 2 nodes), handle these cases straightforwardly by direct observation — if there's only one node, the diameter is 0, and for two nodes, it is 1.

By applying the above approach, we efficiently track and determine the longest path between nodes in the tree, effectively calculating the diameter. Such problems highlight the power of depth-first search (DFS) in dealing with tree-based data structures, leveraging recursion to simplify depth and path calculations.

Solutions

class Solution {
    private int maxDiameter;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        calculateMaxPath(root);
        return maxDiameter;
    }
    private int calculateMaxPath(TreeNode node){
        if(node == null) return 0;
        int leftMax = calculateMaxPath(node.left);
        int rightMax = calculateMaxPath(node.right);
    
        maxDiameter = Math.max(maxDiameter, leftMax + rightMax);
    
        return Math.max(leftMax, rightMax) + 1;
    }
}