543. Diameter of Binary Tree || LeetCode

 The Diameter of the Binary Tree is nothing but the Width of the Binary Tree. In this problem, we need to find a Maximum Path Between Two Ends of Nodes. The Longest Path may exist either only in the Left Part of the Root Node or either only in the Right Part of the Root Node or Combination of the Left Part and Right Part and Root Node. To find the Diameter of the Binary Tree, the prerequisite is to know how to calculate the Maximum Depth of the Binary Tree. We need to do some small changes in the code to find the Diameter of the Binary Tree.

Approach:  

 

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].

Let us consider the above sample input of LeetCode.  We use Recursion to solve this problem. Let's start with the Traversal from the Root Node, we will check if its Left Part and Right Part are Null or not. If it is Null we will simply return the Root Node. As in the above example, it is not Null. We will now Traverse in the Left Part of the Binary Tree. The Height of the Left Part of the Root Node is stored in a variable known as 'LH' and The Height of the Right Part of the Root Node is stored in a variable known as 'RH'. As we need to find Longest Path between two nodes, we Introduce a new variable 'answer' which is initialized to Zero. Now we need to find the Maximum of 'answer' and Height of the Left Part['LH'] +  Height of the Right Part['RH']. This will keep track of the Maximum Path found between two ends of nodes. At last, we need to return the Maximum  Height of the Left Part and Right Part and add '1' to it so that it returns the Height of the Current Node. 

Intution:

Code: 

class Solution {

    int ans=0;

    public int diameterOfBinaryTree(TreeNode root) {

        height(root); 

        return ans;

    } 

    public int height(TreeNode root) {

         if(root==null)

            return 0;

        int lh = height(root.left);

        int rh = height(root.right);

        ans=Math.max(ans,lh+rh);

        return 1+Math.max(lh,rh);

    }

}