Photo by Markus Spiske on Unsplash

# [LeetCode] 129. Sum Root to Leaf Numbers

## Python | Iterative solution (dfs + stack) | Detailed Explanations

## Table of contents

**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
```