/**
* 1. Determine total height(node to leaf distance)at each node and replace
*    the node's value with node's calculated height.
* 2. Determine the maxDiameter by doing a postOrder Traversal.
* 3. The maxDiameter at any node is the max(maxDiameterAtCurrentNode, maxDiameterOnLeftNode, maxDiameterOnRightNode).
*/

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        setMaxHeightOfTreeAtEachNode(root);
        return maxDiameter(root, 0);
    }

    public int setMaxHeightOfTreeAtEachNode(TreeNode root){
        if(root == null){
            return 0;
        }
        root.val = Math.max(setMaxHeightOfTreeAtEachNode(root.left) ,
                            setMaxHeightOfTreeAtEachNode(root.right)) + 1;
        return root.val;
    }

    public int maxDiameter(TreeNode root, int maxDiameter){
        if(root == null){
            return 0;
        }
        int maxDiameterOnLeft = maxDiameter(root.left, maxDiameter);
        int maxDiameterOnRight = maxDiameter(root.right, maxDiameter);
        int maxDiameterAtThisNode = 0;
        if(root.left != null){
            maxDiameterAtThisNode = maxDiameterAtThisNode + root.left.val;
        }
        if(root.right != null){
            maxDiameterAtThisNode = maxDiameterAtThisNode + root.right.val;
        }

        maxDiameter = Math.max(maxDiameter, maxDiameterAtThisNode);
        maxDiameter = Math.max(maxDiameter, maxDiameterOnLeft);
        maxDiameter = Math.max(maxDiameter, maxDiameterOnRight);

        return maxDiameter;
    }
}