#543.Diameter of Binary Tree [LeetCode Grind 75 in Java]

class Solution {

    private int diameter = 0;

    //diameter is longest length between any two nodes
    public int longestLen(TreeNode node){
        if(node == null) return 0;

        //longest length on the left subtree and right subtree
        int left = longestLen(node.left);
        int right = longestLen(node.right);

        //diameter including the node in its path = left + right
        diameter = Math.max(diameter , left + right);

        int longPath = Math.max(left , right);

        //add 1 to include the path from node to its parent
        return longPath + 1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        longestLen(root);
        return diameter;
    }


}