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
Leave a Reply