Tree —Sum Root to Leaf Numbers

(Medium)

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution

Prerequisites

There are three DFS ways to traverse the tree: preorder, postorder and inorder. Please check two minutes picture explanation, if you don’t remember them quite well: here is Python version and here is Java version.

Optimal Strategy to Solve the Problem

Root-to-left traversal is so-called DFS preorder traversal. To implement it, one has to follow straightforward strategy Root->Left->Right.

Since one has to visit all nodes, the best possible time complexity here is linear. Hence all interest here is to improve the space complexity.

There are 3 ways to implement preorder traversal: iterative, recursive and Morris.

Iterative and recursive approaches here do the job in one pass, but they both need up to O(H)O(H) space to keep the stack, where HH is a tree height.

Morris approach is two-pass approach, but it’s a constant-space one.

Intuition

Here we implement standard iterative preorder traversal with the stack:

• Push root into stack.
• While stack is not empty:
• Pop out a node from stack and update the current number.
• If the node is a leaf, update root-to-leaf sum.
• Push right and left child nodes into stack.
• Return root-to-leaf sum.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Solution:

# 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:
        sum_to_leaf = 0
        stack = [(root, 0)]
        
        while stack:
            node , current_num = stack.pop()
            if node:
                current_num = current_num * 10 + node.val
                
                if not node.left and not node.right:
                    sum_to_leaf += current_num
                else:
                    stack.append((node.right, current_num))
                    stack.append((node.left, current_num))
                    
        return sum_to_leaf

Recursive implementation:

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def preorder(root, num):
            nonlocal sum_to_leaf
            if root:
                num = num * 10 + root.val
                # if it's a leaf, update sum_to_leaf sum
                if not root.left and not root.right:
                    sum_to_leaf += num
                preorder(root.left, num)
                preorder(root.right, num)
            
        
        sum_to_leaf = 0
        preorder(root, 0)
        return sum_to_leaf

Success

Runtime: 16 ms, faster than 100.00% of Python3 online submissions for Sum Root to Leaf Numbers.

Memory Usage: 14.5 MB, less than 27.23% of Python3 online submissions for Sum Root to Leaf Numbers.

Complexity Analysis

• Time complexity: O(N) since one has to visit each node.
• Space complexity: up to O(H) to keep the stack, where H is a tree height.