{"id":11206,"date":"2020-04-30T05:21:19","date_gmt":"2020-04-30T05:21:19","guid":{"rendered":"http:\/\/www.softwareeverydayblog.com\/?p=11206"},"modified":"2020-04-30T05:22:03","modified_gmt":"2020-04-30T05:22:03","slug":"programming-problem-deepest-leaves-sum","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11206","title":{"rendered":"[Programming Problem] Deepest Leaves Sum"},"content":{"rendered":"<p>Given a binary tree, return the sum of values of its deepest leaves.<\/p>\n<p>Example 1:<\/p>\n<p><a href=\"https:\/\/www.softwareeverydayblog.com\/wp-content\/uploads\/2020\/04\/Screen-Shot-2020-04-29-at-10.14.37-PM.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.softwareeverydayblog.com\/wp-content\/uploads\/2020\/04\/Screen-Shot-2020-04-29-at-10.14.37-PM-e1588223693483.png\" alt=\"\" width=\"400\" height=\"294\" class=\"alignnone size-full wp-image-11207\" \/><\/a><\/p>\n<p>Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]<br \/>\nOutput: 15<\/p>\n<p>[<a href=\"https:\/\/leetcode.com\/problems\/deepest-leaves-sum\/\" rel=\"noopener noreferrer\" target=\"_blank\">Problem Link<\/a>]<\/p>\n<p>Algorithm<\/p>\n<ul>\n<li>Traverse through the tree using a level variable (which tells you which level you&#8217;re at).<\/li>\n<li>When you reach a leaf, maintain a key map of level->sum.<\/li>\n<li>In the end, pick the highest key from the map and output the value (as result).<\/li>\n<\/ul>\n<p>Also TIL, that <a href=\"https:\/\/www.stefanjudis.com\/today-i-learned\/property-order-is-predictable-in-javascript-objects-since-es2015\/\" rel=\"noopener noreferrer\" target=\"_blank\">Property order is predictable in JavaScript objects since ES2015<\/a>. Quoting from this article &#8220;All properties that are integer indices appear first in the overall object property order and are sorted numerically.&#8221;. This means we don&#8217;t need to sort the leaf map (by key) before returning the result.<\/p>\n<pre lang=\"javascript\">\r\n\/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val, left, right) {\r\n *     this.val = (val===undefined ? 0 : val)\r\n *     this.left = (left===undefined ? null : left)\r\n *     this.right = (right===undefined ? null : right)\r\n * }\r\n *\/\r\n\/**\r\n * @param {TreeNode} root\r\n * @return {number}\r\n *\/\r\n\r\nvar calcLeafMap = function(root, level, leafMap) {\r\n    if (!root) return;\r\n    if (!root.left && !root.right) {\r\n        if (!leafMap[level]) leafMap[level] = 0;\r\n        leafMap[level] += root.val;\r\n    }    \r\n    calcLeafMap(root.left, level+1, leafMap);\r\n    calcLeafMap(root.right, level+1, leafMap);\r\n};\r\n\r\nvar deepestLeavesSum = function(root) {\r\n    let leafMap = {};\r\n    calcLeafMap(root, 0, leafMap);\r\n    let sortedLevels = Object.keys(leafMap);\r\n    return leafMap[sortedLevels[sortedLevels.length-1]];\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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&#8217;re at). When you reach a leaf, maintain a key map of level->sum. In the end, pick the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11206","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11206","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11206"}],"version-history":[{"count":3,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11206\/revisions"}],"predecessor-version":[{"id":11210,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11206\/revisions\/11210"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11206"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11206"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}