Teaching Kids Programming – Breadth First Search Algorithm to Sum Root to Leaf Numbers in Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given the root of a binary tree containing digits from 0 to 9 only. Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

   1
  /
 2
  \
   3

Return the total sum of all root-to-leaf numbers. A leaf node is a node with no children.

Breadth First Search to Sum Root to Leaf

We can traverse the binary tree in Breadth First Search using a queue data structure. We can keep updating the digit/current value from root to current node and need to store this data along with the node in the queue.

When we have met the leaf node (which doesn’t have any children) – we accumulate the sum with the current value from root.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 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 sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque([(root, root.val)])
        ans = 0
        while len(q) > 0:
            p, x = q.popleft()
            if p.left is None and p.right is None:
                ans += x
            if p.left:
                q.append((p.left, x * 10 + p.left.val))
            if p.right:
                q.append((p.right, x * 10 + p.right.val))
        return ans

# 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 sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque([(root, root.val)])
        ans = 0
        while len(q) > 0:
            p, x = q.popleft()
            if p.left is None and p.right is None:
                ans += x
            if p.left:
                q.append((p.left, x * 10 + p.left.val))
            if p.right:
                q.append((p.right, x * 10 + p.right.val))
        return ans

The time complexity is O(N) where N is the number of the nodes in the binary tree (as we need to visit exactly once for each node) and the space complexity is O(N) as we are using a queue to implement the BFS.

Other root to leaves sum:

• Teaching Kids Programming – Depth First Search Algorithm to Sum the Root to Leaf Numbers in Binary Tree
• How to Sum the Root To Leaf in Binary Numbers in a Binary Tree using Breadth First Search?
• Teaching Kids Programming – Breadth First Search Algorithm to Sum Root to Leaf Numbers in Binary Tree
• GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —