# Binary Tree Sum Of Nodes Using C++

Filed Under: C++ In today’s article, we will learn to solve the problem of the binary tree sum of nodes using C++. It is a very active problem as far as the interviews are concerned. Recently Google asked about this problem during a STEP Intern interview. It shows the importance of tree data structures for interviews. Top companies like Google, Facebook, Amazon, and Microsoft are more inclined towards trees and priority queues. So without wasting any time, let’s quickly head toward the problem statement.

Also read: Sieve Of Eratosthenes Using C++

## Problem Statement

You are given a binary tree, write a function that will replace the value at each node by the sum of its children. You need not change the leaf nodes. Children here imply all the descendants of the root node.

For example,

```Input Tree:
(17)
/    \
(9)      (70)
/    \
(1)     (27)

Output:
(124)
/    \
(9)      (98)
/    \
(1)     (27)

Input Tree:
(7)
/   \
(9)    (2)
/   \      \
(10)    (25)   (1)

Output Tree:
(54)
/   \
(44)    (3)
/   \      \
(10)    (25)   (1)

Input Tree:
(7)
/   \
(3)     (4)

Ouput Tree:
(14)
/   \
(3)     (4)
```

Also read: Binary Trees BFS Traversal In C++

## Concept of Binary Tree Sum Of Nodes

While working with trees, we tend to use a recursive algorithm most of the time. Trees algorithms are always of the form described below.

```void tree_algorithm(Node *root)
{
// base case
if(root == NULL)
{
return;
}

// recursive case
// do something with the root node

// next make a recursive call on the left subtree
tree_algorithm(root->left)

// similarly, make a recursive call on the right subtree
tree_algorithm(root->right)
}
```

### Structure Of The Binary Tree

In our case, the structure of the binary tree will be of the following type.

```class Node
{
public:
int data;
Node *left;
Node *right;

Node(int data): data(data), left(NULL), right(NULL) {};
};

void build_tree(Node *&root)
{
// take the input
int data;
cin >> data;

// if the input == -1
// stop taking input for
// this node
if(data == -1)
return;

root = new Node(data);

// recursively build the left subtree
build_tree(root->left);

// recursively build the right subtree
build_tree(root->right);

return;
}

void print_inorder(Node *root)
{
if(root == NULL)
return;

// otherwise, print left
// then print the node
// then right subtree
print_inorder(root->left);
cout << root->data << " ";
print_inorder(root->right);

return;
}
```

### Algorithm of Binary Tree Sum of Nodes

The algorithm is really simple, just follow the steps given below to write the algorithm.

• If the root == NULL
• return 0;
• Else, we will do the following logic.
• root->data += sum_of_nodes(root->left) + sum_of_nodes(root->right);
• Finally return root->data.
• That’s it. The algorithm is this small only.
```void print_inorder(Node *root)
{
if(root == NULL)
return;

// otherwise, print left
// then node
// then right subtree
print_inorder(root->left);
cout << root->data << " ";
print_inorder(root->right);

return;
}
```

## Binary Tree Sum Of Nodes Using C++ Program

```#include <iostream>

using namespace std;

class Node
{
public:
int data;
Node *left;
Node *right;

Node(int data): data(data), left(NULL), right(NULL) {};
};

void build_tree(Node *&root)
{
// take the input
int data;
cin >> data;

// if the input == -1
// stop taking input for
// this node
if(data == -1)
return;

root = new Node(data);

// recursively build the left subtree
build_tree(root->left);

// recursively build the right subtree
build_tree(root->right);

return;
}

void print_inorder(Node *root)
{
if(root == NULL)
return;

// otherwise, print left
// then node
// then right subtree
print_inorder(root->left);
cout << root->data << " ";
print_inorder(root->right);

return;
}

int sum_of_nodes(Node *root)
{
// base case
if(root == NULL)
{
return 0;
}

// recursive case
root->data += sum_of_nodes(root->left) + sum_of_nodes(root->right);

return root->data;
}

int main()
{
cout << "Enter the tree, press -1 to terminate any branch" << endl;

Node *root = NULL;
build_tree(root);

cout << "The inorder print of the tree is:" << endl;
print_inorder(root);
cout << endl;

cout << "The tree after sum of nodes is:" << endl;
sum_of_nodes(root);
print_inorder(root);
cout << endl;
return 0;
}
```

## Conclusion

In this article, we learned to find the sum of nodes of a binary tree using a recursive approach. The algorithm is just a two steps process. The code is simple, that’s the beauty of recursive algorithms. That’s all for today, thanks for reading.