Breadth First Search Algorithm to Compute the Sum of a Binary Tree

Given a binary tree root, return the sum of all values in the tree.

Constraints
n ≤ 100,000 where n is the number of nodes in root

Algorithm to Compute the Tree Sum using BFS

Let’s perform a Breadth First Search Algorithm to traverse the binary tree in level-by-level order. Then we can accure the sum when we visit a node. We use a queue to store the nodes of the same level and push nodes of next level into the queue.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def treeSum(self, root):
        if root is None:
            return 0
        q = deque()
        q.append(root)
        ans = 0
        while len(q) > 0:
            p = q.popleft()
            ans += p.val
            if p.left:
                q.append(p.left)
            if p.right:
                q.append(p.right)
        return ans

The time complexity is O(N) and the space complexity is also O(N) where N is the number of the nodes in the given binary tree.

–EOF (The Ultimate Computing & Technology Blog) —