Teaching Kids Programming – Recursive Depth First Search Algorithm to Find the Sum of Deepest Leaves in a Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

binary-tree

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

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

Constraints:
The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 100

Hints:
Traverse the tree to find the max depth.
Traverse the tree again to compute the sum required.

Recursive Depth First Search Algorithm to Find the Sum of Deepest Leaves in a Binary Tree

We can perform a Depth First Search Traversal on the Binary Tree and accumulate the sum for each level. We store the sums in a hash map (dictionary) where the keys are levels and values are the corresponding sums.

With DFS, we can do pre-order, in-order, post-order, reverse-in-order etc which do not matter, as long as we pass down the levels in the Recursion. We can also implement the DFS using stack in an iterative manner.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        data = defaultdict(int)
        
        def dfs(root, lvl):
            if not root:
                return
            data[lvl] += root.val
            dfs(root.left, lvl + 1)
            dfs(root.right, lvl + 1)
        
        dfs(root, 0)
        return data[max(data.keys())]

Each node in the binary tree is visited once and thus the time complexity is O(N). The space complexity is O(H) where H is the height of the binary tree and in worst cases, the H is equal to N.

See also: Teaching Kids Programming – Breadth First Search Algorithm to Find the Sum of Deepest Leaves in a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —