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.

&nbsp;
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


&nbsp;
Constraints:


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


class Solution:
    """
    Top Down recursion approach: it is sub optimal
    """
    def __init__(self):
        self.max_diameter = 0
    def diameter(self, root):
        if root is None:
            return 0
        return self.max_depth(root.left) + self.max_depth(root.right)

    def max_depth(self, root):
        if root is None:
            return 0
        return 1 + max(self.max_depth(root.left), self.max_depth(root.right))

    def func(self, root):
        if root is not None:
            diameter = self.diameter(root)
            if self.max_diameter < diameter:
                self.max_diameter = diameter
            self.diameterOfBinaryTree(root.left)
            self.diameterOfBinaryTree(root.right)

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.func(root)
        return self.max_diameter

    """
    Better Approach: I can try to approach this problem using bottom up recursion
    """
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        def fun(root):
            if root is None:
                return 0
            left = fun(root.left)
            right = fun(root.right)
            if left + right > self.diameter:
                self.diameter = left + right
            return max(left, right) + 1
        fun(root)
        return self.diameter
class Solution {
    // Declare Global Variable ans to 0
    int ans = 0;
    // Depth First Search Function
    public int dfs(TreeNode root) {
        if(root == null) return 0;
        // recursive call for left height
        int lh = dfs(root.left);
        // recursive call for right height
        int rh = dfs(root.right);

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

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

    // Diameter of Binary Tree Function
    public int diameterOfBinaryTree(TreeNode root) {
        // Call dfs Function
        dfs(root);
        return ans;
    }
}

// Output -
/*
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].
*/

// Time & Space Complexity -
/*
Time - O(n)
Space - O(n)
*/
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        height(root, diameter);
        return diameter;
    }
private:
    int height(TreeNode* node, int& diameter) {
        if (!node) {
            return 0;
        }
        int lh = height(node->left, diameter);
        int rh = height(node->right, diameter);
        diameter = max(diameter, lh + rh);
        return 1 + max(lh, rh);
    }
};
function fastDiameter(node) {
    if(node == null) {
        let pair = new Array(2).fill(0)
        pair[0] = 0
        pair[1] = 0
        return pair
    }
    
    let leftPair = fastDiameter(node.left)
    let rightPair = fastDiameter(node.right)
    
    let leftDiameter = leftPair[0]
    let rightDiameter = rightPair[0]
    
    let height = leftPair[1] + rightPair[1] + 1
    
    let maxDiameter = Math.max(leftDiameter,rightDiameter,height)
    
    let maxHeight = Math.max(leftPair[1],rightPair[1]) + 1
    
    return [maxDiameter,maxHeight]
}

// diameter --> number of edges between two end nodes
var diameterOfBinaryTree = function(root) {
    
    let pair = fastDiameter(root)
    
    return pair[0]-1
};
Diameter of Binary Tree