Sum of nodes at maximum depth of a Binary Tree

Hello Everyone,

Given a root node to a tree, find the sum of all the leaf nodes which are at maximum depth from root node.

While traversing the nodes compare the level of the node with max_level (Maximum level till the current node). If the current level exceeds the maximum level, update the max_level as the current level. If the max level and current level are the same, add the root data to the current sum. if the level is less than max_level, do nothing.

// Code to find the sum of the nodes

// which are present at the maximum depth.

#include <bits/stdc++.h>

using namespace std;

int sum = 0, max_level = INT_MIN;

struct Node

{

int d;

Node *l;

Node *r;

};

// Function to return a new node

Node* createNode( int d)

{

Node *node;

node = new Node;

node->d = d;

node->l = NULL;

node->r = NULL;

return node;

}

// Function to find the sum of the node

// which are present at the maximum depth.

// While traversing the nodes compare the level

// of the node with max_level

// (Maximum level till the current node).

// If the current level exceeds the maximum level,

// update the max_level as current level.

// If the max level and current level are same,

// add the root data to current sum.

void sumOfNodesAtMaxDepth(Node *ro, int level)

{

if (ro == NULL)

return ;

if (level > max_level)

{

sum = ro -> d;

max_level = level;

}

else if (level == max_level)

{

sum = sum + ro -> d;

}

sumOfNodesAtMaxDepth(ro -> l, level + 1);

sumOfNodesAtMaxDepth(ro -> r, level + 1);

}

// Driver Code

int main()

{

Node *root;

root = createNode(1);

root->l = createNode(2);

root->r = createNode(3);

root->l->l = createNode(4);

root->l->r = createNode(5);

root->r->l = createNode(6);

root->r->r = createNode(7);

sumOfNodesAtMaxDepth(root, 0);

cout << sum;

return 0;

}

Output :

22