# Wei-Lin Cheng  # Time and space complexity

O(n) time | O(n) space — where n is the number of nodes of the binary tree

# Submission Detail

Runtime: 32 ms, faster than 72.26% of Python3 online submissions for Sum Root to Leaf Numbers.
Memory Usage: 14.2 MB, less than 79.39% of Python3 online submissions for Sum Root to Leaf Numbers.

# Code and explanation

``````def sumNumbers(self, root: Optional[TreeNode]) -> int:
# Create a stack to store the nodes we are going to traverse.
# For each node, we also store the current number sums up to
# the parent node of current node. So we use 0 as the initial
# value since current number sumps up to the parenat node of
# root is zero.
nodeStack = [[root, 0]]
res = 0

# When the node stack is not empty, keep popping out the last
# item in the stack
while nodeStack:
# Get the current node and current number from the stack
currentNode, currentNum = nodeStack.pop()

# Check if this node exist
if currentNode:
# Add the current node vale into the current number
# which sums up from root node to the current node
currentNum += currentNode.val

# If there's no left and right child node, it means
# the current node is a leaf node.
# Then we can add the current number to the result.
if not currentNode.left and not currentNode.right:
res += currentNum

# Next, append the left child and right child to the
# node stack. When goes to the next level, we need to
# time current num by 10 since it represent the number
# of next digit
nodeStack.append([currentNode.left, currentNum * 10])
nodeStack.append([currentNode.right, currentNum * 10])

# Once traverse all the node in stack, we can return the result
return res
``````