Posted on by Kalkicode
Code Binary Tree

# Sum of all nodes in a binary tree

In this article, we will explore the problem of finding the sum of all nodes in a binary tree. A binary tree is a hierarchical data structure consisting of nodes, each of which has at most two child nodes, referred to as the left child and the right child. The task at hand is to traverse the binary tree and calculate the sum of all the values stored in its nodes. We will provide list of program that solves this problem using recursion and explain the algorithm step by step.

## Problem Statement

Given a binary tree, we need to calculate the sum of all the nodes in the tree.

## Description

Let's begin by understanding the problem with the help of a sample binary tree. Consider the following binary tree:

``````
6
/ \
/   \
2     3
/ \     \
8  -7     1
/     / \
6     4   5``````

We want to find the sum of all the values in this tree. In this case, the sum would be:

Sum = 6 + 2 + 3 + 8 - 7 + 1 + 6 + 4 + 5 = 28

## Idea to Solve the Problem

To calculate the sum of all nodes in a binary tree, we can use a recursive approach. The idea is to start at the root node and recursively calculate the sum of values in the left subtree, the sum of values in the right subtree, and add the value of the current node. We continue this process until we have visited all nodes in the tree.

## Standard Pseudocode

Let's outline the pseudocode for finding the sum of all nodes in a binary tree:

``````function nodeSum(node):
if node is null:
return 0
leftSum = nodeSum(node.left)   // Calculate sum of left subtree
rightSum = nodeSum(node.right) // Calculate sum of right subtree
return leftSum + rightSum + node.data // Add current node's value``````

## Algorithm Explanation

2. If the current node is null (i.e., we have reached a leaf or an empty subtree), we return 0.
3. We recursively calculate the sum of values in the left subtree by calling `nodeSum(node.left)` and store it in `leftSum`.
4. Similarly, we calculate the sum of values in the right subtree by calling `nodeSum(node.right)` and store it in `rightSum`.
5. Finally, we return the sum of `leftSum`, `rightSum`, and the value of the current node, which gives us the sum of all nodes in the tree rooted at the current node.

## Time Complexity of the Code

The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node in the tree exactly once, and the work done at each node is constant time.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post