Algorithms Problem Solving: Deepest Leaves Sum
Tags: algorithms, python, computerscience, interview
Published: 2020-06-06 13:58:27

---
title: Algorithms Problem Solving: Deepest Leaves Sum
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/sakura.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/deepest-leaves-sum.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem description

This is the [Deepest Leaves Sum](https://leetcode.com/problems/deepest-leaves-sum) problem. The description looks like this:

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

## Examples

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

## Solution

My first idea was to organize the tree node values into a hash map. The tree's level as the key and a list of node values as the value.

For this tree example

```python
							  10           ---> level 1
   							/    \
   					 	   5      20       ---> level 2
					     /   \   /   \
	                    2     7 15    22   ---> level 3
```

The hash map will look like this:

```python
{
	1: [10],
	2: [5, 20],
	3: [2, 7, 15, 22]
}
```

- The first level is only the value 10
- The second level is a lista of 5 and 20
- And the third level is 2, 7, 15, and 22

We build this with a helper function.

```python
def helper(node, mapper, level):
    if level in mapper:
        mapper[level] = mapper[level] + [node.val]
    else:
        mapper[level] = [node.val]

    if node.left:
        mapper = helper(node.left, mapper, level + 1)

    if node.right:
        mapper = helper(node.right, mapper, level + 1)

    return mapper
```

The first thing is to verify if the level is in the mapper. If it is, add the current node's value into the list for this level. Otherwise, just set a list with only the current value.

Then traverse the list to the left if it has a left child. And traverse to the right if it has a right child.

We finish the helper algorithm by returning the mapper. Now we have the map with all the tree data separate by level.

We just need to get the deepest level from this map, get the list from the map, and then sum all the values from the list.

```python
def sum_deepest_leaves(root):
    mapper = helper(root, {}, 1)
    deepest_level = 1

    for level in mapper:
        if level > deepest_level:
            deepest_level = level

    deepest_level_nodes_values = mapper[deepest_level]

    nodes_values_sum = 0

    for node_value in deepest_level_nodes_values:
        nodes_values_sum += node_value

    return nodes_values_sum
```

## Resources

- [Learning Python: From Zero to Hero](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)

- [Big-O Notation For Coding Interviews and Beyond](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond?aff=x8bV)
- [Learn Python from Scratch](https://www.educative.io/courses/learn-python-from-scratch?aff=x8bV)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)
- [Big-O Notation For Coding Interviews and Beyond](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond?aff=x8bV)
- [Learn Python from Scratch](https://www.educative.io/courses/learn-python-from-scratch?aff=x8bV)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)