Find the sum of all nodes in a binary tree

In this article, we will use this algorithm to find the sum of all nodes in a binary tree. We have already discussed the Level Order Binary Tree Traversal in Python.

How to find the sum of all nodes in a binary tree?

To find the sum of all nodes in a binary tree, we will traverse each node of the binary tree and find their sum. In this article, we will use a modification of the level order tree traversal algorithm to find the sum of all the nodes. For this task, we will maintain a variable to keep the sum and after processing each node, we will add its value to the sum. 

For example, the sum of the elements of the following binary tree is 150.

Algorithm to find the sum of all nodes in a binary tree

As stated earlier, we will use the algorithm for level order tree traversal to formulate the algorithm to find the sum of all the elements of the binary tree. The algorithm can be formulated as follows. The algorithm takes the root of the binary tree as input and gives the sum of all the elements as output.

1. If the root is empty, return.
2. Let Q be a queue.
3. Initialize the sum to 0.
4. Insert root into the Q.
5. Take out a node from Q.
6. If the node is empty, go to 10. Else, go to 7.
7. Add the element in the node to sum.
8. Insert left child of the node into Q.
9. Insert the right child of the node into Q.
10. Check if Q is empty. If Q is not empty, go to 5.

Implementation of the algorithm in Python

As we have discussed the algorithm, we will implement the algorithm in Python and execute it on the binary tree given in the above figure.

from queue import Queue

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


def insert(root, newValue):
    # if binary search tree is empty, make a new node and declare it as root
    if root is None:
        root = BinaryTreeNode(newValue)
        return root
    # binary search tree is not empty, so we will insert it into the tree
    # if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValue < root.data:
        root.leftChild = insert(root.leftChild, newValue)
    else:
        # if newValue is greater than value of data in root, add it to right subtree and proceed recursively
        root.rightChild = insert(root.rightChild, newValue)
    return root


def sumOfNodes(root):
    if root is None:
        return 0
    Q = Queue()
    Q.put(root)
    current_sum = 0
    while not Q.empty():
        node = Q.get()
        if node is None:
            continue
        current_sum = current_sum + node.data
        Q.put(node.leftChild)
        Q.put(node.rightChild)
    return current_sum


root = insert(None, 15)
insert(root, 10)
insert(root, 25)
insert(root, 6)
insert(root, 14)
insert(root, 20)
insert(root, 60)
print("Printing the sum of all the elements of the binary tree.")
print(sumOfNodes(root))

Output:

Printing the sum of all the elements of the binary tree.
150

Conclusion

In this article, we have discussed the algorithm to find the sum of all the elements of a binary tree. Stay tuned for more articles on the implementation of different algorithms in Python.