LeetCode: Diameter of Binary Tree

Question

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.

Answer 1

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.

Answer 2

According to letcode submissions tab:

                                        Runtime   Memory
Original solution form the question      108 ms    25   MB
Solution from this answer (no recursion) 104 ms    26   MB
Solution form Martin R answer            100 ms    25.3 MB
Solution from this answer (recursive)     84 ms    24.7 MB

Solution recursive

public class DiameterOfBinaryTreeClass
    {
        private int MaxD = 0;

        public int DiameterOfBinaryTree(TreeNode root)
        {
            Height(root);
            return MaxD;
        }

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

            int l = Height(root.left);
            int r = Height(root.right);
            int d = l + r;
            if (d > MaxD)
                MaxD = d;

            return Math.Max(l, r) + 1;
        }
    }

No recursion solution:

private int MaxD = 0;

public int DiameterOfBinaryTree(TreeNode root) {
 Solve(root);
 return MaxD;
}

class CalcNode {
 public sbyte Direction;
 public int Left;
 public int Right;
 public TreeNode TreeNode;
}

private void Solve(TreeNode root) {
 if (root == null)
  return;

 var stack = new Stack < CalcNode > ();

 stack.Push(new CalcNode() {
  Direction = 0, Left = 0, Right = 0, TreeNode = root
 });
 HashSet < TreeNode > usedTreeNodes = new HashSet < TreeNode > ();

 while (stack.Count != 0) {
  TreeNode cur = stack.Peek().TreeNode;
  if (cur.left != null && !usedTreeNodes.Contains(cur.left)) {
   stack.Push(new CalcNode() {
    Direction = -1, Left = 0, Right = 0, TreeNode = cur.left
   });
   continue;
  }

  if (cur.right != null && !usedTreeNodes.Contains(cur.right)) {
   stack.Push(new CalcNode() {
    Direction = 1, Left = 0, Right = 0, TreeNode = cur.right
   });
   continue;
  }

  CalcNode removedNode = stack.Pop();
  usedTreeNodes.Add(removedNode.TreeNode);
  int d = removedNode.Left + removedNode.Right;
  if (d > MaxD)
   MaxD = d;

  if (removedNode.Direction == 0)
   continue;

  CalcNode curCalcNode = stack.Peek();
  int removedNodeHeight = Math.Max(removedNode.Left, removedNode.Right) + 1;
  if (removedNode.Direction == 1)
   curCalcNode.Right += removedNodeHeight;
  else
   curCalcNode.Left += removedNodeHeight;
 }
}
}