DESCRIPTION:
In this program we are finding the sum of all the nodes in a perfect binary tree.
Perfect binary tree is a tree with every leaf node at the same depth and degree 2.

INPUT:

                1
               / \
              3   4
             / \ / \
            5  6 7  8

OUTPUT:

Sum of the elements is 1+3+4+5+6+7+8=28

CODE:

/* Program to find sum of all the nodes of the given perfect binary tree */


#include<iostream>
using namespace std; 

template <typename T>//When the data is other than string then this template will be used
struct Value
{
   T data;
   Value()
   {
      data = 0;
   }
};

template <>	//When the data is string then this template will be used
struct Value <string>
{
   string data;
   Value()
   {
      data.assign("");
   }
};

template <typename T>		//creating a new node
struct Node
{
   Value<T> data;
   Node<T>* left=nullptr;
   Node<T>* right=nullptr;
};


template <typename T>		//function template to create binary tree
Node<T>* createTree()
{
  //creating all nodes needed in the binary tree
   Node<T>* node1 = new Node<T>; 
   node1->data.data = 1;
   Node<T>* node2 = new Node<T>; 
   node2->data.data = 2;
   Node<T>* node3 = new Node<T>; 
   node3->data.data = 3;
   Node<T>* node4 = new Node<T>;
   node4->data.data = 4;
   Node<T>* node5 = new Node<T>; 
   node5->data.data = 5;
   Node<T>* node6 = new Node<T>; 
   node6->data.data = 6;
   Node<T>* node7 = new Node<T>; 
   node7->data.data = 7;
   
  //connecting nodes to create a binary tree
   node1->left = node2;
   node1->right = node3;
   node2->left = node4;
   node2->right = node5;
   node3->left = node6;
   node3->right = node7;
   
   

   return node1;	//returning the root node as it is connected to every node
}

template <typename T>	  
int Sum(Node<T>* root)    //function to traverse all the elements and add them
{ 
    if (root == NULL) 
        return 0; 
    return (root->data.data + Sum(root->left) + Sum(root->right)); 
} 
  
int main() 
{ 
    Node<int>* root = createTree<int>();  //creating tree
  
    int sum = Sum(root); 
    cout << "Sum of all the elements is: " << sum << endl; 
  
    return 0; 
} 

OUTPUT: