Deepest Leaves Sum

Find the sum of values of its deepest leaves.

Example 1:

    3
   / \
  9  20
    /  \
   15   7

Input: root = [3,9,20,null,null,15,7]
Output: 22

Approach

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class DeepestLeavesSum {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3);
        tree.left = new TreeNode(9);
        tree.right = new TreeNode(20);
        tree.right.left = new TreeNode(15);
        tree.right.right = new TreeNode(7);
        int sum = deepestLeavesSum(tree);
        System.out.println(sum);
    }

    // function to find the sum of deepest leaf nodes
    // in the binary tree
    static int deepestLeavesSum(TreeNode root) {
        // if tree is empty
        if (root == null)
            return 0;
        // queue to hold the incoming
        // nodes
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(root);
        List<Integer> v = new ArrayList<>();

        // iterate till the queue is non
        // empty
        while (!q.isEmpty()) {

            // find the size of queue
            int len = q.size();
            v.clear();
            // iterate till the length of queue
            while (len > 0) {
                len--;
                root = q.poll();
                v.add(root.val);

                // store the left if exist
                if (root.left != null)
                    q.add(root.left);

                // store the right if exist
                if (root.right != null)
                    q.add(root.right);
            }
        }
        int sum = 0;

        // find the sum of deepest leaf nodes
        for (int i = 0; i < v.size(); i++)
            sum += v.get(i);
        return sum;

    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};


//function to find the sum of deepest leaf nodes
//in the binary tree
int deepestLeavesSum(TreeNode* root) 
{
      //if tree is empty
        if(root==NULL)
               return 0;
       //queue to hold the incoming
       //nodes
       queue<TreeNode*> q;
       q.push(root);
       vector<int> v;

       //iterate till the queue is non
       //empty
      while(!q.empty())
        {

             //find the size of queue
            int len=q.size();
            v.clear();
            //iterate till the length of queue
            while(len--)
            {
                root=q.front();
                q.pop();
                v.push_back(root->data);

                //store the left if exist
                if(root->left)
                      q.push(root->left);

                //store the right if exist
                if(root->right)
                      q.push(root->right);
            }
        }
        int sum=0;

        //find the sum of deepest leaf nodes
        for(int i=0;i<v.size();i++)
               sum+=v[i];
        return sum;

}
int main()
{
    TreeNode *root=new TreeNode(1);
    root->left=new TreeNode(2);
    root->right=new TreeNode(3);
    root->left->left=new TreeNode(4);
    root->left->right=new TreeNode(5);
    root->right->right=new TreeNode(6);
    root->right->right->right=new TreeNode(8);
    root->left->left->left=new TreeNode(7);
    int sum=deepestLeavesSum(root);
    cout<<sum<<"\n";
    return 0;
}