[Google Question][LeetCode] Deepest Leaves Sum

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

Example:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 1 <= Node.val <= 100

Approach: We can use preorder traversal. We can take current level and max depth as parameters in the recursive method:

• If current level is equal to max depth, add the node's value to result sum. 
• if current level is more than max depth then that means we have calculated sum for wrong level so we make the result sum as 0 and assign current level to max depth.
• if current level is less than max depth, we don't need to change result sum or max depth.

That's all.

Implementation in C#:

    public int DeepestLeavesSum(TreeNode root) 

    {

        if (root == null)

        {

            return 0;

        }

        int maxDepth = 0;

        int leavesSum = 0;

        this.DeepestLeavesSum(root, 0, ref maxDepth, ref leavesSum);

        return leavesSum;

    }

    

    private void DeepestLeavesSum(TreeNode node, int currLevel, ref int maxDepth, ref int leavesSum)

    {

        if (node == null)

        {

            return;

        }

        if (currLevel > maxDepth)

        {

            maxDepth = currLevel;

            leavesSum = 0;

        }

        if (currLevel == maxDepth)

        {

            leavesSum += node.val;

        }

        this.DeepestLeavesSum(node.left, currLevel + 1, ref maxDepth, ref leavesSum);

        this.DeepestLeavesSum(node.right, currLevel + 1, ref maxDepth, ref leavesSum);

    }

Complexity: O(n)