Sum of nodes at maximum depth of a Binary Tree | Set 2
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> |
22
Complexity Analysis:
- Time Complexity: O(N) where N is the number of vertices in the binary tree.
- Auxiliary Space: O(N).