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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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 2^n-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⁽ⁿ⁺¹⁾-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 -

• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree
• Binary Array Sorting

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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!