## Introduction

A leaf node is a node in the binary tree which doesnâ€™t have any child node. It is the node at which that particular branch of the binary tree ends. Since there can be different branches with different lengths, the maximum depth of a given binary tree is that of the branch with the most levels. For example,

8

/ \

16 7

/ \ /

20 4 30

/

9

In the above binary tree, 4, 30 and 9 are all leaf nodes, but 9 is the only leaf node at the maximum depth.

Now, letâ€™s discuss how to find the sum of the leaf nodes at the maximum depth of a given binary tree.

### Problem Statement

In this problem, we have to find the sum of the leaf nodes at the maximum depth of a given binary tree.

### Sample Examples

```
Input:
The given binary tree is
5
/ \
10 15
/ \ / \
20 25 30 35
Output:
110
Explanation:
The leaf nodes at the maximum depth of the given binary tree are 20, 25, 30 and 35. Their sum is 110.
```

## Brute Force Approach

In this approach, we keep track of the apparent maximum depth with the mx_lvl variable. If we get to a depth higher than the current value of mx_lvl, we update its value. If the current depth is smaller than mx_lvl, we can ignore this nodeâ€™s value. If the current depth is the same as mx_lvl, we add the value of the node to the sum.

### Steps of Algorithm

- We take care of the rare case when the binary tree is empty first. In this case, the root node would be null, and there will be no sum.
- We then initialise a variable mx_lvl to keep track of the apparent maximum depth. As we donâ€™t know its value yet, we give it the lowest value possible. If the current depth is greater than mx_lvl, we update mx_lvlâ€™s value to that of the current depth.
- If the depth of the level is equal to that of mx_lvl, we add the value of this node to the sum variable. In case the depth is lower than mx_lvl, we ignore the node.
- We recursively initialise this function for each of the root nodeâ€™s child nodes until there are no more child nodes and we have reached the maximum depth. The value of the sum variable would give us the sum of the leaf nodes at the maximum depth of the given binary tree.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int sum = 0, mx_lvl = INT_MIN;
struct Node {
int data;
Node *left;
Node *right;
};
Node* createNode(int data) {
Node *node;
node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void MaxDepthSum(Node *root, int level) {
if(root == NULL)
return;
if(level > mx_lvl) {
sum = root->data;
mx_lvl = level;
}
else if(level == mx_lvl) {
sum = sum + root->data;
}
MaxDepthSum(root->left, level + 1);
MaxDepthSum(root->right, level + 1);
}
int main() {
Node *root;
root = createNode(5);
root->left = createNode(10);
root->right = createNode(15);
root->left->left = createNode(20);
root->left->right = createNode(25);
root->right->left = createNode(30);
root->right->right = createNode(35);
MaxDepthSum(root, 0);
cout << "The sum of the max depth nodes is " << sum;
return 0;
}
```

**Output:**

`The sum of the max depth nodes is 110`

#### Complexity Analysis

**Time Complexity:** O(N)

**Explanation: **The code will run for every new node, so the time complexity is O(N).

**Space Complexity:** O(N)

**Explanation: **In this approach, space is needed for every node, so the space complexity is O(N).