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

  1. We start with the root of the binary tree.
  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.

Code Solution

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.

New Comment