[Programming Problem] Deepest Leaves Sum

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

Example 1:

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

[Problem Link]

Algorithm

  • Traverse through the tree using a level variable (which tells you which level you’re at).
  • When you reach a leaf, maintain a key map of level->sum.
  • In the end, pick the highest key from the map and output the value (as result).

Also TIL, that Property order is predictable in JavaScript objects since ES2015. Quoting from this article “All properties that are integer indices appear first in the overall object property order and are sorted numerically.”. This means we don’t need to sort the leaf map (by key) before returning the result.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 
var calcLeafMap = function(root, level, leafMap) {
    if (!root) return;
    if (!root.left && !root.right) {
        if (!leafMap[level]) leafMap[level] = 0;
        leafMap[level] += root.val;
    }    
    calcLeafMap(root.left, level+1, leafMap);
    calcLeafMap(root.right, level+1, leafMap);
};
 
var deepestLeavesSum = function(root) {
    let leafMap = {};
    calcLeafMap(root, 0, leafMap);
    let sortedLevels = Object.keys(leafMap);
    return leafMap[sortedLevels[sortedLevels.length-1]];
};

softwareeveryday

9,656 thoughts on “[Programming Problem] Deepest Leaves Sum”

  139. It’s one of the most recognized aphoristic statements today.
    This aphorism is short and sweet, but it teaches us a valuable truth.
    The complete quote was, A Jack of all trades and master of none, but oftentimes better than a master of one.
    Why is this stuff important.
    Not only that, but you can use aphorisms in your writing to summarize your central theme.
    The term aphorism originates from late Latin aphorismus and Greek aphorismos.
    The early bird gets the worm.
    Another aphorism that’s adapted is, Don’t count your chickens before they hatch.
    It’s one of the most recognized aphoristic statements today.
    Washington also said, It is better to offer no excuse than a bad one.
    People often use this quote when discussing health, but Franklin was talking about fire safety.
    Today, calling someone a Jack of all trades is usually a jab because it implies that their knowledge is superficial.
    Aphoristic statements also appear in everyday life, such as daily speeches made by politicians and leaders.
    An aphorism is a literary device that uses a short, clever saying to express a general truth.
    Your wish is my command.
    Because let’s face it, perseverance is the key to success in life.

    Reply

  141. Keep your friends close, but your enemies closer.
    Sandys said, Honestie the best policie, which in modern English is…
    The complete quote was, A Jack of all trades and master of none, but oftentimes better than a master of one.
    Let’s talk about that.
    For example.
    Aphorisms are so common that we hardly think twice about them.
    Examples of Aphorism in Literature
    It originally read, Count not they chickens that unhatched be…
    But Yoda isn’t having it.
    Like George Washington, Sandys believed that telling the truth is always the way to go.
    Other Common Examples of Aphorisms
    Why is this stuff important.
    Aphorisms can act as a guideline to help narrow the focus of your work.
    Too many times to count, right.
    Brevity is the key.
    This famous motto highlights the truism that life is full of ups and downs.

    Reply

  173. If you do, you agree with George Herbert’s famous aphorism from his book, Outlandish Proverbs.
    This famous motto highlights the truism that life is full of ups and downs.
    He knows that Luke should either decide that he can do it or decide to quit.
    This aphorism is short and sweet, but it teaches us a valuable truth.
    He once stated, If you want a thing done well, do it yourself.
    ’Ah, all things come to those who wait,’
    So my advice.
    They’re in social media captions all over the web.
    Brevity is the key.
    Fall seven times, stand up eight.
    The idea is simple.
    Honesty is the best policy.
    Sometimes, though.
    Not good.
    Give it a try!
    How many times have you heard one of the following aphorism examples.

    Reply

  282. Thought I would comment and say great theme, did you design it on your own? Its really great!Thank you for the great info! I would never have gotten this by myself!I m having a weird problem I cannot subscribe your rss feed, I m using google reader fyi sdfsdkfpjşsmlfsdfdskj

    Reply

  283. Good work, I am a big believer in leaving comments on blogs to help the blog writers know that theyve added something useful to the internet!First Off, let me commend your clearness on this subject sdfsdkfpjşsmlfsdfdskj

    Reply