3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
 }
}
}
\$\endgroup\$
  • \$\begingroup\$ Maybe, generally iteration is preferred over recursion. Can you show that/if iteration is feasible? \$\endgroup\$ – JAD Oct 15 at 11:24
  • \$\begingroup\$ the code would be more complex, but the question was about peformance (not about a code simplisity) sure i can provide an example. Will do it in the next few days. \$\endgroup\$ – user2809176 Oct 15 at 11:43
  • \$\begingroup\$ @JAD i decided to write recursive version first. With the next update I will unfold the recursion - it would be interesting to see the performance impact :) \$\endgroup\$ – user2809176 Oct 16 at 7:58
  • \$\begingroup\$ My not recursive solution turned out to be slower as the recursive version \$\endgroup\$ – user2809176 Oct 18 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.