Leetcode 129 Sum Root to Leaf Numbers

Problem Link

https://leetcode.com/problems/sum-root-to-leaf-numbers/

Discussion

As input, the root of a binary tree is given. What we need to do that,

Explore all the paths from the root to the leaf
Each root->leaf makes a number, need to take all possible numbers
Return the summation of all the numbers made by root->leaf paths

Solution

Here we will solve it in two different approaches. The first one is using BFS. And next one is using DFS.

Solution - BFS

BFS means breadth-first search, this algorithm works on trees by traveling a tree level by level. When each possible height's nodes are visited then it goes to the next level.

So to solve this problem we have to take a variable : totalSum that will be returned at the end of the code and initially the value of totalSum is set to 0.

To solve using BFS we will take a queue, initially, we will keep the root and the value of the root as a tuple in the queue.

We are taking the root's value to track the number and taking the root as we need to traverse the left and right child via the root.
Until the queue is empty, we will pop elements from the queue and traverse the subtrees.
Each node with its value is kept in the queue to make sure all nodes are visited, and we have to calculate as root.val*10+root.left.val to get a decimal number. This way whenever we will reach a leaf, we will get the number this whole path made.
In the end, we need to sum up all the numbers from left and right subtrees and return it

Code ( BFS )

Let's jump into code, and try to simulate how this code works using pen and paper, executing some self-made examples to understand better.

# 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: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # sum of all the possible numbers make by root to leaf paths
        totalSum = 0
        # keep nodes and values to queues
        q = [(root,root.val)]
        while q:
            # each time a node and its value is popped
            node, val = q.pop(0)
            # there is no left or right nodes means we have reached to the leaf. So jsut add the value to total sum
            if not node.left and not node.right:
                totalSum += val
            # in the queue, we are not keeping the node along with it's own value 
            # but the decimal number it's created in the nth node
            if node.left :
                q.append([node.left, val*10+node.left.val])

            if node.right :
                q.append([node.right, val*10+node.right.val])

        return totalSum

Solution using DFS

To traverse a tree using DFS (Depth First Search) algorithm means after starting we will keep traversing nodes not level by level but until we find the leaf node. So recursive approach is used in DFS.

Other logical stuff is the same as discussed in the previous BFS-based solution. Just the approach to traverse is different here. So let's jump into code :

Code ( DFS )

# 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: Optional[TreeNode]) -> int:
        def dfs(root, preSum):
            if not root:
                return 0
            # calculating the number the root->leaf path created in the current node
            totalSum = preSum*10+root.val
            # no child means we reached to a leaf node
            if not root.left and not root.right:
                return totalSum
            # recursively get the sum of left and right child
            leftSum = dfs(root.left, totalSum)
            rightSum = dfs(root.right, totalSum)

            return leftSum+rightSum
        # initially total sum is set to 0
        return dfs(root,0)

Complexity

As we are visiting each node once, the time complexity is O(n) and in the worst case, the space complexity is O( n ) where n denotes the total nodes.

Thanks for reading. Let me know any confusion in the comments.

UH's blog