Binary Tree Sum Of Nodes Using C++

Filed Under: C++
Binary Tree Sum Of Nodes Using 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;
}
Binary Tree Sum Of Nodes Code
Binary Tree Sum Of Nodes Code

Output

Binary Tree Sum Of Nodes Output
Binary Tree Sum Of Nodes Output

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.

Further Readings

To learn more about stacks, trees and recursion, you can visit the following articles.

https://www.journaldev.com/56852/binary-trees-bfs-traversal-cpp

https://www.journaldev.com/61078/reverse-a-stack-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content