Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is space complexity?
4.2.
What is the maximum number of possible nodes at depth n of a binary tree?
4.3.
What are the maximum and the minimum number of total possible nodes for a binary tree of depth n?
5.
Conclusion
Last Updated: Mar 27, 2024

Find the Sum of nodes at maximum depth of a Binary Tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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.

Source

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

  1. 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.
  2. 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.
  3. 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.
  4. 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In this approach, we first calculate the maximum depth of the given binary tree. Then we input this value along with the binary tree’s root to the sum calculating function. This approach makes the tree traversal faster as now we can ignore all the values except the ones at the maximum depth and add those to the sum.

Steps of Algorithm

  1. First, we find the maximum depth of the given binary tree. We do that by using a recursive function that traverses the whole tree and increments a variable on each level. The maximum this variable can go will give us the maximum depth.
  2. Once we have the maximum depth, we can initialise the sum function. The sum function will recursively traverse the tree, decrementing the value of the maximum depth variable with every level traversed until it reaches 1. At this point, the function is at the maximum depth.
  3. The values of the nodes at the maximum depth are added to a sum variable. This variable will 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;
 
struct Node {
    int data;
    Node *left, *right;

    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int MaxDepthSum(Node* node, int max) {
    if (node == NULL)
        return 0;
    if (max == 1)
        return node->data;
    return MaxDepthSum(node->left, max - 1) +
        MaxDepthSum(node->right, max - 1);
}

int maxDepth(Node* node) {
    if (node == NULL)
        return 0;
    return 1 + max(maxDepth(node->left),
                    maxDepth(node->right));    
}
 
int MaxLevelSum(Node* root) {
    int MaxDepth = maxDepth(root);
    return MaxDepthSum(root, MaxDepth);
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(10);
    root->right = new Node(15);
    root->left->left = new Node(20);
    root->left->right = new Node(25);
    root->right->left = new Node(30);
    root->right->right = new Node(35);

    cout << "The sum of the max depth nodes is " << (MaxLevelSum(root)) << endl;
}

 

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).

Frequently Asked Questions

What is space complexity?

The algorithm's total memory space, including input values for execution, is referred to as space complexity.

What is the maximum number of possible nodes at depth n of a binary tree?

The maximum number of possible nodes at depth n is 2n-1 nodes.

What are the maximum and the minimum number of total possible nodes for a binary tree of depth n?

The maximum number of total possible nodes for a binary tree of depth n is 2(n+1)-1, and the minimum number of total possible nodes is n+1.

Conclusion

In conclusion, we discussed different approaches to find the sum of the leaf nodes at the maximum depth of a given binary tree. For every approach, we discussed algorithms and complexities. We eventually saw how each of the methods are different from the others.

 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Find the Increasing subsequence of length three with maximum product
Next article
Clone a Binary Tree with Random Pointers
Live masterclass