Teaching Kids Programming – Depth First Search Algorithm to Sum the 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.

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

For example:

    1
   / \
  3   5
 /
9

The sum the root to leaf numbers for this binary tree should be 139+15=154

Yesterday we talked about the Breadth First Search algorithm to solve this problem: Algorithms to Compute the Sibling Value in Binary Tree. We can also use the Depth First Search to tackle this problem as well.

Depth First Search Algorithm to Sum the Root to the Leaf Numbers

Using DFS, we traverse the binary tree (or graph) as far as we can go. When we reach the leaf nodes, we sum it. In order to achieve this, we would need to carry over the current number from root.

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

# 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:
        ans = 0
        def dfs(root, cur):
            nonlocal ans
            if root is None:
                return 
            if root.left is None and root.right is None:
                ans += cur * 10 + root.val
                return
            dfs(root.left, cur * 10 + root.val)
            dfs(root.right, cur * 10 + root.val)
        dfs(root, 0)
        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:
        ans = 0
        def dfs(root, cur):
            nonlocal ans
            if root is None:
                return 
            if root.left is None and root.right is None:
                ans += cur * 10 + root.val
                return
            dfs(root.left, cur * 10 + root.val)
            dfs(root.right, cur * 10 + root.val)
        dfs(root, 0)
        return ans

This DFS uses a “nonlocal” keyword to reference a local variable which is not in current local function. This is kinda “global” to the DFS local function. We can tune the function to make it return the sum to leaf nodes from the current root.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 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:
        def dfs(root, cur):
            if root is None:
                return 0
            if root.left is None and root.right is None:
                return cur * 10 + root.val
            return dfs(root.left, cur * 10 + root.val) + \
                    dfs(root.right, cur * 10 + root.val)
        return dfs(root, 0)

# 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:
        def dfs(root, cur):
            if root is None:
                return 0
            if root.left is None and root.right is None:
                return cur * 10 + root.val
            return dfs(root.left, cur * 10 + root.val) + \
                    dfs(root.right, cur * 10 + root.val)
        return dfs(root, 0)

This is a more elegant solution that doesn’t require summing to a ‘global’ variable. Both DFS implementations are O(N) time as we need to visit exactly once for each node in the binary tree. The space complexity is O(N) as we are using Recursion due to implicit use of a stack.

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) —