Sum of nodes at maximum depth of a Binary Tree | Set 2

0 0 5 minutes read

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

Example:

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

Input : root(of above tree)
Output : 22

Explanation:
Nodes at maximum depth are: 4, 5, 6, 7. 
So, sum of these nodes = 22

In the previous article we discussed a recursive solution which first finds the maximum level and then finds the sum of all nodes present at that level.
In this article we will see a recursive solution without finding the height or depth. The idea is that 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 otherwise if level is less than max_level, do nothing.

Below is the implementation of the above approach:

C++

// C++ Program to find sum of nodes at maximum
// Depth of the Binary Tree
 
#include <bits/stdc++.h>
using namespace std;
 
// Variables to store sum and
// maximum level
int sum = 0, max_level = INT_MIN;
 
// Binary Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;
};
 
// Utility function to create and
// return a new Binary Tree Node
Node* createNode(int val)
{
 
    Node* node = new Node;
 
    node->data = val;
    node->left = NULL;
    node->right = NULL;
 
    return node;
}
 
// Function to find the sum of the node which
// are present at the maximum depth
void sumOfNodesAtMaxDepth(Node* root, int level)
{
    if (root == NULL)
        return;
 
    // If the current level exceeds the
    // maximum level, update the max_level
    // as current level.
    if (level > max_level) {
        sum = root->data;
        max_level = level;
    }
 
    // If the max level and current level
    // are same, add the root data to
    // current sum.
    else if (level == max_level) {
        sum = sum + root->data;
    }
 
    // Traverse the left and right subtrees
    sumOfNodesAtMaxDepth(root->left, level + 1);
    sumOfNodesAtMaxDepth(root->right, level + 1);
}
 
// Driver Code
int main()
{
    Node* root;
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
 
    sumOfNodesAtMaxDepth(root, 0);
 
    cout << sum;
 
    return 0;
}

Java

// Java Program to find sum of nodes at maximum 
// Depth of the Binary Tree 
 
class GfG 
{
 
// Variables to store sum and 
// maximum level 
static int sum = 0,
    max_level = Integer.MIN_VALUE; 
 
// Binary Tree Node 
static class Node 
{ 
    int data; 
    Node left; 
    Node right; 
}
 
// Utility function to create and 
// return a new Binary Tree Node 
static Node createNode(int val) 
{ 
 
    Node node = new Node(); 
    node.data = val; 
    node.left = null; 
    node.right = null; 
 
    return node; 
} 
 
// Function to find the sum of 
// the node which are present
// at the maximum depth 
static void sumOfNodesAtMaxDepth(Node root, 
                                int level) 
{ 
    if (root == null) 
        return; 
 
    // If the current level exceeds the 
    // maximum level, update the max_level 
    // as current level. 
    if (level > max_level) 
    { 
        sum = root.data; 
        max_level = level; 
    } 
 
    // If the max level and current level 
    // are same, add the root data to 
    // current sum. 
    else if (level == max_level) 
    { 
        sum = sum + root.data; 
    } 
 
    // Traverse the left and right subtrees 
    sumOfNodesAtMaxDepth(root.left, level + 1); 
    sumOfNodesAtMaxDepth(root.right, level + 1); 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
    Node root = null; 
    root = createNode(1); 
    root.left = createNode(2); 
    root.right = createNode(3); 
    root.left.left = createNode(4); 
    root.left.right = createNode(5); 
    root.right.left = createNode(6); 
    root.right.right = createNode(7); 
 
    sumOfNodesAtMaxDepth(root, 0); 
    System.out.println(sum); 
}
} 
 
// This code is contributed by 
// Prerna Saini.

Python3

# Python3 Program to find sum of nodes at maximum
# Depth of the Binary Tree
 
# Variables to store sum and
# maximum level
sum = [0]
max_level = [-(2**32)]
 
# Binary tree node 
class createNode: 
     
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
 
# Function to find the sum of the node which
# are present at the maximum depth
def sumOfNodesAtMaxDepth(root, level):
    if (root == None):
        return
     
    # If the current level exceeds the
    # maximum level, update the max_level
    # as current level.
    if (level > max_level[0]):
        sum[0] = root.data
        max_level[0] = level
         
    # If the max level and current level
    #are same, add the root data to
    # current sum.
    elif (level == max_level[0]):
        sum[0] = sum[0] + root.data
         
    # Traverse the left and right subtrees
    sumOfNodesAtMaxDepth(root.left, level + 1)
    sumOfNodesAtMaxDepth(root.right, level + 1)
     
# Driver Code
root = createNode(1)
root.left = createNode(2)
root.right = createNode(3)
root.left.left = createNode(4)
root.left.right = createNode(5)
root.right.left = createNode(6)
root.right.right = createNode(7)
 
sumOfNodesAtMaxDepth(root, 0)
 
print(sum[0])
 
# This code is contributed by SHUBHAMSINGH10

C#

// C#  Program to find sum of nodes at maximum 
// Depth of the Binary Tree
using System;
public class GfG 
{ 
 
    // Variables to store sum and 
    // maximum level 
    static int sum = 0, 
        max_level = int.MinValue; 
 
    // Binary Tree Node 
    class Node 
    { 
        public int data; 
        public Node left; 
        public Node right; 
    } 
 
    // Utility function to create and 
    // return a new Binary Tree Node 
    static Node createNode(int val) 
    { 
 
        Node node = new Node(); 
        node.data = val; 
        node.left = null; 
        node.right = null; 
 
        return node; 
    } 
 
    // Function to find the sum of 
    // the node which are present 
    // at the maximum depth 
    static void sumOfNodesAtMaxDepth(Node root, 
                                    int level) 
    { 
        if (root == null) 
            return; 
 
        // If the current level exceeds the 
        // maximum level, update the max_level 
        // as current level. 
        if (level > max_level) 
        { 
            sum = root.data; 
            max_level = level; 
        } 
 
        // If the max level and current level 
        // are same, add the root data to 
        // current sum. 
        else if (level == max_level) 
        { 
            sum = sum + root.data; 
        } 
 
        // Traverse the left and right subtrees 
        sumOfNodesAtMaxDepth(root.left, level + 1); 
        sumOfNodesAtMaxDepth(root.right, level + 1); 
    } 
 
    // Driver Code 
    public static void Main() 
    { 
        Node root = null; 
        root = createNode(1); 
        root.left = createNode(2); 
        root.right = createNode(3); 
        root.left.left = createNode(4); 
        root.left.right = createNode(5); 
        root.right.left = createNode(6); 
        root.right.right = createNode(7); 
 
        sumOfNodesAtMaxDepth(root, 0); 
        Console.WriteLine(sum); 
    } 
} 
 
/* This code is contributed PrinciRaj1992 */

Javascript

<script>
 
    // JavaScript Program to find sum of nodes at maximum 
    // Depth of the Binary Tree 
     
    // Variables to store sum and 
    // maximum level 
    let sum = 0;
    let max_level = Number.MIN_VALUE; 
     
    // Binary Tree Node 
    class Node
    {
        constructor(val) {
           this.left = null;
           this.right = null;
           this.data = val;
        }
    }
     
    // Utility function to create and 
    // return a new Binary Tree Node 
    function createNode(val) 
    { 
 
        let node = new Node(val); 
        return node; 
    } 
 
    // Function to find the sum of 
    // the node which are present
    // at the maximum depth 
    function sumOfNodesAtMaxDepth(root, level) 
    { 
        if (root == null) 
            return; 
 
        // If the current level exceeds the 
        // maximum level, update the max_level 
        // as current level. 
        if (level > max_level) 
        { 
            sum = root.data; 
            max_level = level; 
        } 
 
        // If the max level and current level 
        // are same, add the root data to 
        // current sum. 
        else if (level == max_level) 
        { 
            sum = sum + root.data; 
        } 
 
        // Traverse the left and right subtrees 
        sumOfNodesAtMaxDepth(root.left, level + 1); 
        sumOfNodesAtMaxDepth(root.right, level + 1); 
    } 
     
    let root = null; 
    root = createNode(1); 
    root.left = createNode(2); 
    root.right = createNode(3); 
    root.left.left = createNode(4); 
    root.left.right = createNode(5); 
    root.right.left = createNode(6); 
    root.right.right = createNode(7); 
   
    sumOfNodesAtMaxDepth(root, 0); 
    document.write(sum); 
 
</script>

Output

Complexity Analysis:

Time Complexity: O(N) where N is the number of vertices in the binary tree.
Auxiliary Space: O(N).

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!