3
\$\begingroup\$

Given a binary tree, return the sum of values of its deepest leaves.

enter image description here

Constraints:

The number of nodes in the tree is between 1 and 10^4. The value of nodes is between 1 and 100.

Please review for performance and style

using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/deepest-leaves-sum/
    /// </summary>

    [TestClass]
    public class DeepestLeavesSumTest
    {
        [TestMethod]
        public void ExampleTest()
        {
            var root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            root.left.left.left = new TreeNode(7);
            root.right = new TreeNode(3);
            root.right.right = new TreeNode(6);
            root.right.right.right = new TreeNode(8);
            DeepestLeavesSumClass deepest = new DeepestLeavesSumClass();
            Assert.AreEqual(15, deepest.DeepestLeavesSum(root));
        }
    }

    public class DeepestLeavesSumClass
    {

        int maxDepth = 0;
        int sum = 0;
        public int DeepestLeavesSum(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }
            DFS(root, 0);
            return sum;
        }

        private void DFS(TreeNode root, int depth)
        {
            if (root == null)
            {
                return;
            }
            if (maxDepth < depth + 1)
            {
                maxDepth = depth + 1;
                sum = root.val;
            }
            else if (depth + 1 == maxDepth)
            {
                sum += root.val;
            }
            DFS(root.left, depth + 1);
            DFS(root.right, depth + 1);
        }
    }

}
\$\endgroup\$
5
  • \$\begingroup\$ if you give -1 please explain why, I would like to learn. \$\endgroup\$ – Gilad Apr 10 '20 at 21:14
  • \$\begingroup\$ In a binary tree formatted as in your given input data, each layer starts at a number of type \$2^{depth} - 1\$, so you don't even need to perform a DFS, and only \$O(1)\$ memory is required. \$\endgroup\$ – the default. Apr 11 '20 at 13:17
  • \$\begingroup\$ How? What do you mean \$\endgroup\$ – Gilad Apr 11 '20 at 13:24
  • \$\begingroup\$ The root = [1,2,3,4,5,null,6,7,null,null,null,null,8] part. In such a format, e.g. the third layer starts at index \$2^3 - 1 = 7\$ (and continues till the array ends or the index \$2^4 - 1 = 15\$ exclusive). \$\endgroup\$ – the default. Apr 11 '20 at 13:25
  • \$\begingroup\$ Oh i get what you mean. But the function is givena TreeNode as input \$\endgroup\$ – Gilad Apr 11 '20 at 14:32
2
\$\begingroup\$

This solution seems generally fine although it's not much code to analyze and it's already as succinct as it could reasonably be.

A few suggestions:

  • Avoid naming a class SomethingClass. It's enough that the type is a class; appending types to names adds noise.
  • SumDeepestLeaves sounds more like a method (an action) while DeepestLeavesSum sounds more like a property or attribute.
  • Instead of using depth + 1, use depth. It doesn't matter how you compute the depth as long as it's consistent.
  • Use vertical whitespace before and after all blocks and function definitions.
  • Creating objects is expensive. Worse, introducing state can cause bugs as the method is non-idempotent--the caller can't use the object more than once or results will be incorrect.

    It's an antipattern to have to create an object just to call what seems like a stateless method from the perspective of the caller. Doing:

    DeepestLeavesSumClass deepest = new DeepestLeavesSumClass();
    Assert.AreEqual(15, deepest.DeepestLeavesSum(root));
    

    feels a lot like:

    MathematicsClass mathematics = new MathematicsClass();
    Assert.AreEqual(3, mathematics.Add(1, 2));
    

    I exaggerate, but a static method like:

    Assert.AreEqual(15, BinaryTree.SumDeepestLeaves(root));
    

    is more pleasant and semantically meaningful. An alternative to making it static would be to encapsulate/hide TreeNode as a member of a BinaryTree class, then instantiate the BinaryTree class, populate your nodes and call tree.SumDeepestLeaves() to sum your tree's deepest leaves. This is a bit of a tangent on your current design even if it feels most correct from an OOP perspective.

Basically, you've introduced two class variables on an object as a shortcut in order to keep your algorithm clean and easy to write, but this design adds complexity to the caller and makes the class brittle.

One solution is to use the ref keyword to keep all data local to the calls:

class BinaryTree
{
    public static int SumDeepestLeaves(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }

        int maxDepth = 0;
        int sum = 0;
        SumDeepestLeaves(root, 0, ref maxDepth, ref sum);
        return sum;
    }

    private static void SumDeepestLeaves(TreeNode root, int depth, ref int maxDepth, ref int sum)
    {
        if (root == null)
        {
            return;
        }
        else if (maxDepth < depth)
        {
            maxDepth = depth;
            sum = root.val;
        }
        else if (depth == maxDepth)
        {
            sum += root.val;
        }

        SumDeepestLeaves(root.left, depth + 1, ref maxDepth, ref sum);
        SumDeepestLeaves(root.right, depth + 1, ref maxDepth, ref sum);
    }
}

This is more verbose, but the benefits are worth it. You can also argue that ref makes the programmer's intent clearer to help justify the extra verbosity and added parameters.

Kudos on keeping the recursive helper private. However, a name like DFS seems too generic--it does do a DFS, but it's specific to summing deepest leaves. As the BinaryTree class grows to contain dozens of methods, it'd no longer be obvious from the name that DFS is related to SumDeepestLeaves. Overload the SumDeepestLeaves method so there's no doubt.

You can also do this using a BFS instead of recursion using the level-order trick where each iteration on the queue dumps the entire level, queuing up the next round and summing the current. This isn't definitely better, but at least there's no refs and no helper function, so all the logic is in one place, and it's worth knowing about in any case.

class BinaryTree 
{
    public int SumDeepestLeaves(TreeNode root) 
    {
        if (root == null)
        {
            return 0;
        }

        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int sum = 0;

        while (queue.Count() > 0)
        {
            sum = 0;

            for (int i = queue.Count() - 1; i >= 0; i--) 
            {
                TreeNode curr = queue.Dequeue();
                sum += curr.val;

                if (curr.left != null) 
                {
                    queue.Enqueue(curr.left);
                }

                if (curr.right != null)
                {
                    queue.Enqueue(curr.right);
                }
            }
        }

        return sum;
    }
}
\$\endgroup\$
3
\$\begingroup\$

Rename DFS to DeepestLeavesSum.

Extract depth + 1 to variable.

In here else if (depth + 1 == maxDepth) the else is reduant.

The order of depth + 1 and maxDepth is different between the Ifs. One time maxDepth is on the left side and other time on the right side.

Usually, when writing recursion, you return the value and not store it in the class.

If you call DeepestLeavesSum twice with the same object the second call will return wrong results because it will use sum and maxDepth of the first call. A good practice is avoiding saving state.

\$\endgroup\$

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.