# Sum of nodes at maximum depth of a Binary Tree

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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Calculate the max depth of the given tree. Now, start traversing the tree similarly as traversed during maximum depth calculation. But, this time with one more argument (i.e. maxdepth), and traverse recursively with decreasing depth by 1 for each left or right call. Wherever max == 1, means the node at max depth is reached. So add its data value to sum. Finally, return sum.

Below is the implementation for above approach:

## Java

 `// Java code for sum of nodes ` `// at maximum depth ` `import` `java.util.*; ` ` `  `class` `Node { ` `    ``int` `data; ` `    ``Node left, right; ` ` `  `    ``// Constructor ` `    ``public` `Node(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `        ``this``.left = ``null``; ` `        ``this``.right = ``null``; ` `    ``} ` `} ` ` `  `class` `GfG { ` ` `  `    ``// function to find the sum of nodes at ` `    ``// maximum depth arguments are node and ` `    ``// max, where max is to match the depth ` `    ``// of node at every call to node, if ` `    ``// max will be equal to 1, means ` `    ``// we are at deepest node. ` `    ``public` `static` `int` `sumMaxLevelRec(Node node, ` `                     ``int` `max) ` `    ``{ ` `        ``// base case ` `        ``if` `(node == ``null``)  ` `            ``return` `0``;      ` ` `  `        ``// max == 1 to track the node ` `        ``// at deepest level ` `        ``if` `(max == ``1``)  ` `            ``return` `node.data;     ` ` `  `        ``// recursive call to left and right nodes ` `        ``return` `sumMaxLevelRec(node.left, max - ``1``) +  ` `               ``sumMaxLevelRec(node.right, max - ``1``); ` `    ``} ` ` `  `    ``public` `static` `int` `sumMaxLevel(Node root) { ` ` `  `        ``// call to function to calculate ` `        ``// max depth ` `        ``int` `MaxDepth = maxDepth(root); ` `         `  `        ``return` `sumMaxLevelRec(root, MaxDepth); ` `    ``} ` ` `  `    ``// maxDepth function to find the ` `    ``// max depth of the tree ` `    ``public` `static` `int` `maxDepth(Node node) ` `    ``{ ` `        ``// base case ` `        ``if` `(node == ``null``)  ` `            ``return` `0``;      ` ` `  `        ``// either leftDepth of rightDepth is ` `        ``// greater add 1 to include height ` `        ``// of node at which call is ` `        ``return` `1` `+ Math.max(maxDepth(node.left),  ` `                           ``maxDepth(node.right));      ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` ` `  `        ``/*      1 ` `              ``/ ` `              ``2   3 ` `            ``/ / ` `            ``4 5 6 7     */` ` `  `        ``// Constructing tree ` `        ``Node root = ``new` `Node(``1``); ` `        ``root.left = ``new` `Node(``2``); ` `        ``root.right = ``new` `Node(``3``); ` `        ``root.left.left = ``new` `Node(``4``); ` `        ``root.left.right = ``new` `Node(``5``); ` `        ``root.right.left = ``new` `Node(``6``); ` `        ``root.right.right = ``new` `Node(``7``); ` ` `  ` `  `        ``// call to calculate required sum ` `        ``System.out.println(sumMaxLevel(root)); ` `    ``} ` `} `

## C#

 `using` `System; ` ` `  `// C# code for sum of nodes  ` `// at maximum depth  ` ` `  `public` `class` `Node ` `{ ` `    ``public` `int` `data; ` `    ``public` `Node left, right; ` ` `  `    ``// Constructor  ` `    ``public` `Node(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `        ``this``.left = ``null``; ` `        ``this``.right = ``null``; ` `    ``} ` `} ` ` `  `public` `class` `GfG ` `{ ` ` `  `    ``// function to find the sum of nodes at  ` `    ``// maximum depth arguments are node and  ` `    ``// max, where max is to match the depth  ` `    ``// of node at every call to node, if  ` `    ``// max will be equal to 1, means  ` `    ``// we are at deepest node.  ` `    ``public` `static` `int` `sumMaxLevelRec(Node node, ``int` `max) ` `    ``{ ` `        ``// base case  ` `        ``if` `(node == ``null``) ` `        ``{ ` `            ``return` `0; ` `        ``} ` ` `  `        ``// max == 1 to track the node  ` `        ``// at deepest level  ` `        ``if` `(max == 1) ` `        ``{ ` `            ``return` `node.data; ` `        ``} ` ` `  `        ``// recursive call to left and right nodes  ` `        ``return` `sumMaxLevelRec(node.left, max - 1)  ` `                ``+ sumMaxLevelRec(node.right, max - 1); ` `    ``} ` ` `  `    ``public` `static` `int` `sumMaxLevel(Node root) ` `    ``{ ` ` `  `        ``// call to function to calculate  ` `        ``// max depth  ` `        ``int` `MaxDepth = maxDepth(root); ` ` `  `        ``return` `sumMaxLevelRec(root, MaxDepth); ` `    ``} ` ` `  `    ``// maxDepth function to find the  ` `    ``// max depth of the tree  ` `    ``public` `static` `int` `maxDepth(Node node) ` `    ``{ ` `        ``// base case  ` `        ``if` `(node == ``null``) ` `        ``{ ` `            ``return` `0; ` `        ``} ` ` `  `        ``// either leftDepth of rightDepth is  ` `        ``// greater add 1 to include height  ` `        ``// of node at which call is  ` `        ``return` `1 + Math.Max(maxDepth(node.left),  ` `                            ``maxDepth(node.right)); ` `    ``} ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `Main(``string``[] args) ` `    ``{ ` ` `  `        ``/*   1  ` `            ``/   ` `            ``2 3  ` `            ``/ /   ` `            ``4 5 6 7  */` ` `  `        ``// Constructing tree  ` `        ``Node root = ``new` `Node(1); ` `        ``root.left = ``new` `Node(2); ` `        ``root.right = ``new` `Node(3); ` `        ``root.left.left = ``new` `Node(4); ` `        ``root.left.right = ``new` `Node(5); ` `        ``root.right.left = ``new` `Node(6); ` `        ``root.right.right = ``new` `Node(7); ` ` `  ` `  `        ``// call to calculate required sum  ` `        ``Console.WriteLine(sumMaxLevel(root)); ` `    ``} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output :

```22
```

Time Complexity: O(N), where N is the number of nodes in the tree.

This article is attributed to GeeksforGeeks.org

Tree Tree

code

load comments