LeetCode: Sum Deepest Leaves

JavaScript Solution Using Level Order Traversal

What's the secret to being an algorithms master? Well, I don't know, I haven't even completed a LeetCode Hard problem yet. But I’ll tell you my strategy for getting better at them: see every single problem that exists.

Ok, that's obviously not possible. But the more you see the better! Also, you don't really need to see every problem, but rather every single type of problem. Have you ever heard the saying “There's no such thing as an original idea”? Apparently, Mark Twain said that; I had to google it. But that's the idea behind algorithms as well. They all use some concept or another from other algorithms. Take comfort in the idea that there is nothing new under the sun. Once you solve one problem, you've actually probably solved a few.

Here is a Leetcode algorithm I recently solved. I’d never seen this problem before but I was able to solve it in no time. It only took writing one or two new lines of code. All because I had seen something similar before.

Problem: Deepest Leaves Sum

This is a LeetCode medium difficulty problem. Given the root of a binary tree, return the sum of values of its deepest leaves. For example, given the binary tree: [1,2,3,4,5,null,6,7,null,null,null,null,8] the return is 15

      1
     / \
    2   3
   / \   \
  4   5   6
 /         \
7           8

The following shows the 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)
}

My Thought Process:

So I started thinking about how I wanted to solve this problem. I looked at the tree and realized, if the tree could be broken up by levels, I was only interested in the lowest level of the tree.

Then my mind immediately went to past problems I have solved. And I remembered doing a problem where I had to print out the nodes of the tree in level order. That's exactly what I need. A way to traverse the tree by levels. Then I could calculate the sum on the lowest level and return that value.

So I used my solution to that previous problem, tweaked it slightly, and voila! I had the solution with minimal work. I was reusing work I had already done. Reusing solutions to subproblems.

Here is a link to a blog I wrote on the Binary Tree Level Order Traversal

BFS Algorithm:

1. To start let’s initialize our queue (with the root node inside) for BFS and also initialize the sum.
2. Inside the while loop (which runs till the queue is empty), we define a for-loop. The for-loop will run for each of the elements in the queue at the end of the last level. This means we will increment “i” until it reaches the queue length.
3. Before the for-loop, be sure to re-initialize the sum for each level by setting it to zero.
4. Inside the for-loop, remove a node from the top of the queue and add its value to the level sum. Add children to the queue, if they exist.
5. Once all the nodes of a level have been visited (the end of the for-loop) we simply move on to the next level of the tree (if there is one). Continue steps until the queue is empty.
6. At the end of the function, simply return the sum value since that was calculated at the lowest level.

JavaScript Code Solution:

var deepestLeavesSum = function(root) {
   let queue = [root]
   let sum=0
   while (queue.length != 0){
      sum =0
      const n = queue.length
      
      for (let i = 0; i < n; i++){
         let curr = queue.pop()
         sum+=curr.val
         curr.left && queue.unshift(curr.left)
         curr.right && queue.unshift(curr.right)
      }
   }
   return sum
};

When I submitted this code on LeetCode, I got the following results:

• Runtime: 112 ms, faster than 49.46% of JavaScript online submissions
• Memory: 48.6 MB, less than 54.50% of JavaScript online submissions

Space-Time Complexity Analysis:

Since each node is visited at least once, the time complexity is O(n). The space complexity is also O(n) since the queue can contain all the leaf nodes in the worst case.

References:

Deepest Leaves Sum - LeetCode

Binary Tree Level Order Traversal

More content at plainenglish.io