Deepest Leaves Sum | LeetCode

Problem Source

Given a binary tree with N nodes. Each node in the binary tree contains some value associated with it. Find the sum of values present in the leaf nodes present at highest depth.

For example for the tree given below, the sum is 7 + 8 = 15. Because and 7 and 8 are the leaf nodes which are at the highest depth

Solution

We can solve this problem easily by visiting each node of the tree recursively and storing the node values at a particular depth in a map.

For the example given above, we will store the following in the map :

0 - > { 1 }
1 -> { 2, 3 }
2 -> {4, 5, 6 }
3 -> { 7, 8 } 

Since the maximum key (depth ) in the map is 3, we will sum the values corresponding to depth 3 which are 7 and 8 and get the answer as 15.

Solution Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
       map<int, int> depthSum;
       dfs(root, 0, depthSum);
       return depthSum.rbegin()->second;
    }
  
    void dfs(TreeNode* root, int depth, map<int, int>& depthSum) {
      if (root == NULL) {
        return;
      }
      
      depthSum[depth] += root->val;
      
      dfs(root->left, depth + 1, depthSum);
      dfs(root->right, depth + 1, depthSum);
    }
};