Sum of Nodes at Maximum Level of Binary Tree in C++

In this article, we will learn how to find the sum of nodes at the maximum level of a binary tree in C++.

Example

Input:
        8
       / \
      7   6
     / \ / \
    3  2 1  4
Output: Sum of nodes at maximum level: 10
Exaplanation: 3+2+1+4 = 10

Input: 
       4
      / \
     2   1
    /
   3
Output: Sum of nodes at maximum level: 3
Exaplanation: 3

C++ program to find Sum of Nodes at Maximum Level of Binary Tree

We are going to solve this problem using a recursive approach.

1. Create a tree using struct.

2. Declare a variable sum=0 to store the sum of nodes at maximum level and max_level=0 to check whether the level is a maximum level.

3. Create a function SumofNodes to calculate the sum of nodes.

• Check the base case when the tree is empty i.e. root==NULL.
• Now check the current level is the maximum level of the given tree, if true add the current node to the sum.
• Else, assgin max_level = level.

4. Recursive call the SumOfNodes of the right subtree and then SumOfNodes of the left subtree i.e

SumOfNodes(root->right, level+1);

SumOfNodes(root->left, level+1);

5. Finally, return the sum.

#include <bits/stdc++.h>
using namespace std;
int sum = 0;
int max_level = 0;
struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};
Node *newNode(int data){
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
void inorder(Node* root){
    if (root == NULL)
    return;
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}
void SumOfNodes(Node* root, int level){
    if (root == NULL)
        return;

    if(level>max_level){
        sum = root->data;
        max_level = level;
    }
    else if(level == max_level){
        sum += root->data;
    }

    SumOfNodes(root->right, level+1);
    SumOfNodes(root->left, level+1);
} 
int main(){
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout<<"The inorder of the given binary tree: "<<endl;
    inorder(root);
    cout<<endl;
    SumOfNodes(root, 0);
    cout<<"The sum of the nodes at the maximum level is: "<<sum;
    return 0;
}

Output

The inorder of the given binary tree: 
4 2 5 1 6 3 7
The sum of the nodes at the maximum level is: 22

Also, read

• Check if a given binary tree is perfect or not in Python
• Height of a binary tree in C++