Deepest Leaves Sum Solution

Leetcode Solution: Understand Leetcode problem Deepest Leaves Sum(1302) Solution

19 September 2020

In this article we’ll be solving the problem: Deepest Leaves Sum. Just like the problem, Same Tree or Equal Tree and Leaf Similar Trees, this problem also requires a slight modification in the Tree Traversal approach to find the deepest nodes.

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

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

Constraints:
    The number of nodes in the tree is between 1 and 10^4.
    The value of nodes is between 1 and 100.

The problem description is very simple here. It is asking us to find the sum of all those leaf nodes that are at the deepest level. We’ll be solving this problem using the Pre Order Tree Traversal method only but we’ll divide it into two parts:

In the first part we’ll find the value of the deepest level.
Traverse the tree once again to find all those leaf nodes that are that the level found in the previous step and sum their values.

Here’s an image showing the steps on the example tree:

In the first step, we’ve found the depth of the tree by finding the node at the lowest depth and then in the second image, we’re calculating the sum of all the nodes that are present at the depth found in the previous step.

Here’s the program to find the deepest node and the depth:

func preOrder(node *TreeNode, depth int) {
    if depth > maxDepth {
        maxDepth = depth
    }
    if node.Left != nil {
        preOrder(node.Left, depth + 1)
    }
    if node.Right != nil {
        preOrder(node.Right, depth + 1)
    }
}

The complete program to solve this problem is here:

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

var maxDepth int
var sum int
func deepestLeavesSum(root *TreeNode) int {
    maxDepth = 0
    sum = 0
    if root == nil {
        return 0
    }
    preOrder(root, 0)
    fmt.Println(maxDepth)
    sumDeep(root, 0)
    return sum
}

func preOrder(node *TreeNode, depth int) {
    if depth > maxDepth {
        maxDepth = depth
    }
    if node.Left != nil {
        preOrder(node.Left, depth + 1)
    }
    if node.Right != nil {
        preOrder(node.Right, depth + 1)
    }
}

func sumDeep(node *TreeNode, depth int) {
    if depth == maxDepth {
        sum += node.Val
    }
    if node.Left != nil {
        sumDeep(node.Left, depth + 1)
    }
    if node.Right != nil {
        sumDeep(node.Right, depth + 1)
    }
}

This program can be found on GitHub as well.

Here the function deepestLeavesSum calls preOrder to find the maximum depth. Once the maximum depth is found then deepestLeavesSum call sumDeep. sumDeep is a pre order tree traversal function in which we’re summing up the values of the nodes that are at the maximum depth found in the preOrder function.

This program is presented in a very simple way and definitely it some optimizations and reductions in the number of lines can be done.

Loading Comments... Disqus Loader

Deepest Leaves Sum Solution

Leetcode Solution: Understand Leetcode problem Deepest Leaves Sum(1302) Solution

Related Pages: