sum-root-to-leaf-numbers.py

#  https://leetcode.com/problems/sum-root-to-leaf-numbers/
#  Related Topics: Tree, DFS
#  Difficulty: Medium


# Initial thoughts:
# Using a DFS approach we are going to traverse every path from the root to its leafs, all
# the while combining the digits at the current node's value. This will be done using basic
# math (numberUntilNow = numberUntilNow * 10 + newDigit).
# Since numbers are value types in Python and for every recursive function call a new copy
# will be created from the number we have created until that point, we don't need to worry
# about the numbers from different paths to get mixed up.
# At the end of the route, when both leafs are null, we are going to return the number.
# Since we are going to add the result of the paths in the left subtree with the path in the
# right subtree, the end result will be the total of all the paths in the binary tree.

# Time complexity: O(n) where n === the number of nodes in the tree
# Space complexity: O(n) where n === the number of noded in the tree (that's a worst case where
# the binary tree is fully unballance and looks like a linked list)

# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        return self.traverse(root, 0)

    def traverse(self, root: TreeNode, number: int) -> int:
        if root == None:
            return 0
        number = number * 10 + root.val
        if root.left == None and root.right == None:
            return number
        return self.traverse(root.left, number) + self.traverse(root.right, number)