Diameter of Binary Tree: Given the root of a binary tree, return the length of the diameter of the tree.

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.

The length of a path between two nodes is represented by the number of edges between them.

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 [0, 10^4].
• -100 <= Node.val <= 100

Try this Problem on your own or check similar problems:

1. Diameter of N-ary Tree
2. Longest Path With Different Adjacent Characters

Solution:

class Solution {
    private class Diameter{
        int value;
        Diameter(int value){
            this.value = value;
        }
    }
    public int diameterOfBinaryTree(TreeNode root) {
        Diameter maxDiameter = new Diameter(0);
        helper(root, maxDiameter);
        return maxDiameter.value;
    }
    private int helper(TreeNode root, Diameter maxDiameter){
        if(root == null) return 0;
        int left = helper(root.left, maxDiameter);
        int right = helper(root.right, maxDiameter);
        maxDiameter.value = Math.max(left + right, maxDiameter.value);
        return Math.max(left, right) + 1;
    }
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

Explanation:

We use the same approach we used for calculating depth in Maximum Depth of Binary Tree , only this time we have one additional line maxDiameter.value = Math.max(left + right, maxDiameter.value);. So the diameter can either be the distance between left most leaf node and root if we don’t have a right subtree or vice-versa, or height of left subtree plus the height of right subtree (think about two nodes that are most distant from each other appearing of course in different subtrees, on different sides of the root). We wrapped primitive type into class wrapper so we can pass it by reference to helper function and keep the best solution throughout recursion stack. You can however have a global variable or use an array of two elements (pair containing height and diameter).