C++ program to sum of nodes on the longest path from the root to a leaf node.














































C++ program to sum of nodes on the longest path from the root to a leaf node.



Description:
     C++ program to sum of nodes on the longest path from the root to a leaf node.
     Assumption: The sum of nodes of the first longest path will be calculated if two paths have the same length.

Algorithm:

     1. Declaring the Structure for the node.
     2. Inserting data of the nodes by using the functions newnode() and insert().
     3. Traversing in the tree and finding if the traversed length is greater then the previous length(denoted by cnt). If so,             then the value of the sum is changed and the new value is allotted to the sum. If not, then the previous value is                 retained.
     4. If the length of 2 paths are same then the first path is taken into consideration according to the assumption.

Program: 
#include<iostream>

using namespace std;

int sum=0,cnt=0; // global variables to find the sum of nodes and their length

// Defining the structure of the node
struct node
{
    int data;
    node *right, *left;
}*root=NULL; // global root node declared

// Inserting data in a new tree
node* newnode(int data)
{
node* temp = new node; // new node is created
temp->data = data;
temp->left = temp->right = NULL; //as for a new node the left and right node stays free
return temp;
}

// Inserting data in a already built tree
node* insert(node *root, int data)
{
if (root == NULL)
return newnode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}

// Inorder traversal of the tree
void inorder(node* root)
{
if (root != NULL)
{
inorder(root->left); // left node first
cout << root->data << " "; // data
inorder(root->right); // then right node
}
}

// Calculating the sum of te nodes of the longest path
void longest_path(node* root,int c,int s) // local variables c & s for calculating each node's length from root and sum till that node
{
    if(root!=NULL)
    {
        c++;
        s+=root->data;
        if(c>cnt) //checking if the new length is greater then changing the values
        {
            sum=s;
            cnt=c;
        }
        longest_path(root->left,c,s); // left traversal
        longest_path(root->right,c,s); // right traversal
    }
}
int main()
{
    int info,choice;
    
    // Choice of the user whether to enter data or not
    while(1)
    {
        cout<<"Enter the data: ";
        cin>>info;
        root=insert(root,info);
        cout<<"Enter 1 for entering data and 0 to stop: ";
        cin>>choice;
        if(choice==0) // user wants no more data
            break;
    }

    inorder(root); // printing of the tree
    
    longest_path(root,0,0); //for the root node the value of sum and length will be 0 at first
    
    cout<<endl;
    cout<<"Length of longest path is: "<<cnt<<endl;
    cout<<"Sum: "<<sum<<endl;
    return 0;
}

Comments