< Back




1302. Deepest Leaves Sum

We need to return the sum of the values for the deepest leaves in a binary tree. To easily do this,
we conduct a breadth-first search until we hit the level were the deepest leaves are. We maintain
two queues, one for future nodes to visit, and one for nodes we're visiting at the current level.

We continue until no more nodes are in the future nodes queue. Once that's the case, we know that
all of the deepest leaves are the in the current level. We sum the values of all the leaves in the
current level and return the sum.

The solution is as follows:


  from collections import deque

  class Solution:
      def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
          queue = deque([root])

          while queue:
              curr_queue, queue = queue, deque()

              for node in curr_queue:
                  if node.left:
                      queue.append(node.left)
                  if node.right:
                      queue.append(node.right)

          return sum([node.val for node in curr_queue])


_ Time Complexity:

  O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

  O(n) - We maintain queues that can store all nodes in the binary tree.