## DEV Community is a community of 665,832 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Deepest Leaves Sum seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

#### Examples:

Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Visual: Example 2:
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`

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

When asked to find information about a particular row of a binary tree, the normal thought is to use a breadth-first search (BFS) approach. A BFS approach usually involves the use of a queue data structure (q) so that we deal with the nodes of the tree in the proper order.

The trick is to deal with a single row at a time by making note of the length of the queue (qlen) when we start the row. Once we've processed that many nodes, we know we've just finished the current row and any remaining entries in q are from the next row. This can be accomplished easily with a nested loop.

In this case, processing a node simply means accumulating the running total (ans) for the row and then moving any children of the node onto the end of the queue.

When we start a new row, we can reset ans back to 0, and then just keep processing rows until q is empty. The last value of ans should be our final answer, so we should return ans.

Alternately, we can use a depth-first search (DFS) approach with recursion to traverse the binary tree. If we pass the row depth (lvl) as an argument to our recursive function (dfs), we can use it to update the values in an array of row sums (sums) by using lvl as an index (sums[lvl]). Then we can simply return the last value of sums as our answer.

#### Implementation:

There are only minor differences between the four languages.

#### Javascript Code:

##### w/ BFS:
``````var deepestLeavesSum = function(root) {
let q = [root], ans, qlen, curr
while (q.length) {
qlen = q.length, ans = 0
for (let i = 0; i < qlen; i++) {
curr = q.shift(), ans += curr.val
if (curr.left) q.push(curr.left)
if (curr.right) q.push(curr.right)
}
}
return ans
};
``````
##### w/ Recursive DFS:
``````var deepestLeavesSum = function(root) {
let sums = []
const dfs = (node, lvl) => {
if (lvl === sums.length) sums[lvl] = node.val
else sums[lvl] += node.val
if (node.left) dfs(node.left, lvl+1)
if (node.right) dfs(node.right, lvl+1)
}
dfs(root, 0)
return sums[sums.length-1]
};
``````

#### Python Code:

##### w/ BFS:
``````class Solution:
def deepestLeavesSum(self, root: TreeNode) -> int:
q, ans, qlen, curr = [root], 0, 0, 0
while len(q):
qlen, ans = len(q), 0
for _ in range(qlen):
curr = q.pop(0)
ans += curr.val
if curr.left: q.append(curr.left)
if curr.right: q.append(curr.right)
return ans
``````
##### w/ Recursive DFS:
``````class Solution:
def deepestLeavesSum(self, root: TreeNode) -> int:
sums = []
def dfs(node: TreeNode, lvl: int):
if lvl == len(sums): sums.append(node.val)
else: sums[lvl] += node.val
if node.left: dfs(node.left, lvl+1)
if node.right: dfs(node.right, lvl+1)
dfs(root, 0)
return sums[-1]
``````

#### Java Code:

##### w/ BFS:
``````class Solution {
public int deepestLeavesSum(TreeNode root) {
int ans = 0, qlen = 0;
while (q.size() > 0) {
qlen = q.size();
ans = 0;
for (int i = 0; i < qlen; i++) {
TreeNode curr = q.poll();
ans += curr.val;
}
}
return ans;
}
}
``````
##### w/ Recursive DFS:
``````class Solution {
List<Integer> sums = new ArrayList<>();
public int deepestLeavesSum(TreeNode root) {
dfs(root, 0);
return sums.get(sums.size()-1);
}
public void dfs(TreeNode node, int lvl) {
else sums.set(lvl, sums.get(lvl) + node.val);
if (node.left != null) dfs(node.left, lvl+1);
if (node.right != null) dfs(node.right, lvl+1);
}
}
``````

#### C++ Code:

##### w/ BFS:
``````class Solution {
public:
int deepestLeavesSum(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int ans = 0, qlen = 0;
while (q.size() > 0) {
qlen = q.size(), ans = 0;
for (int i = 0; i < qlen; i++) {
TreeNode* curr = q.front(); q.pop();
ans += curr->val;
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
}
return ans;
}
};
``````
##### w/ Recursive DFS:
``````class Solution {
public:
vector<int> sums;
int deepestLeavesSum(TreeNode* root) {
dfs(root, 0);
return sums.back();
}
void dfs(TreeNode* node, int lvl) {
if (lvl == sums.size()) sums.push_back(node->val);
else sums[lvl] += node->val;
if (node->left) dfs(node->left, lvl+1);
if (node->right) dfs(node->right, lvl+1);
}
};
``````