LeetCode: Diameter of Binary Tree https://leetcode.com/problems/diameter-of-binary-tree/


  Given a binary tree, you need to compute 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.

Example:
Given a binary tree
          1
         / \
        2   3
       / \     
      4   5  

  
  Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
  
  Note: The length of path between two nodes is represented by the
  number of edges between them.


 [TestClass]
    public class DiameterOfBinaryTreeTest
    {
        [TestMethod]
        public void DiameterOfBinaryTreeTest1()
        {
                        /* Constructed binary tree is
                       1
                     /   \
                   2      3
                 /  \
               4     5
             */
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            root.right = new TreeNode(3);
            DiameterOfBinaryTreeClass diam = new DiameterOfBinaryTreeClass();

            int result = diam.DiameterOfBinaryTree(root);
            Assert.AreEqual(3, result);
        }
}



 //https://leetcode.com/problems/diameter-of-binary-tree/
    public class DiameterOfBinaryTreeClass
    {
        public int DiameterOfBinaryTree(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }

            int leftDiameter = DiameterOfBinaryTree(root.left);
            int rightDiameter = DiameterOfBinaryTree(root.right);

            int leftHeight = Height(root.left);
            int rightHeight = Height(root.right);
            return Math.Max(leftHeight + rightHeight, Math.Max(leftDiameter,rightDiameter));
        }

        private int Height(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }

            return Math.Max(Height(root.left) ,Height(root.right)) + 1;
        }
    }


Please review for performance.
Your method visits mosts nodes twice: Here

int leftDiameter = DiameterOfBinaryTree(root.left);
int rightDiameter = DiameterOfBinaryTree(root.right);

int leftHeight = Height(root.left);
int rightHeight = Height(root.right);


calling DiameterOfBinaryTree on the left and right subtree determines the height of both subtrees, and then calling Height on the subtrees computes those heights again.

This can be improved by defining a helper function which (recursively) computes both height and diameter of a tree rooted at a node:

private (int height, int diam) HeightAndDiameter(TreeNode root)
{
    if (root == null)
    {
        return (0, 0);
    }

    var (leftHeight, leftDiam) = HeightAndDiameter(root.left);
    var (rightHeight, rightDiam) = HeightAndDiameter(root.right);

    return (Math.Max(leftHeight, rightHeight) + 1,
            Math.Max(Math.Max(leftDiam, rightDiam), leftHeight + rightHeight));
}


C# (named) tuples are used here to return both values to the caller. The main function then becomes

public int DiameterOfBinaryTree(TreeNode root)
{
    return HeightAndDiameter(root).diam;
}


Each node is visited exactly once now.