loading...
Cover image for Algorithms Problem Solving: Deepest Leaves Sum

Algorithms Problem Solving: Deepest Leaves Sum

teekay profile image TK Originally published at leandrotk.github.io ・3 min read

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Deepest Leaves Sum problem. The description looks like this:

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

Examples

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

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

The hash map will look like this:

{
    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.

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.

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

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

Posted on Jun 6 by:

teekay profile

TK

@teekay

Sharing knowledge https://leandrotk.github.io/tk

Discussion

markdown guide