# Maximum sum of internal nodes among all levels of the given binary tree

Here given code implementation process.

``````import java.util.HashMap;
// Java program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}

public class BinaryTree
{
public TreeNode root;

public BinaryTree()
{
this.root = null;

}

public void internalNodeSum(TreeNode node,
HashMap<Integer,Integer> record, int level)
{

if(node !=null)
{

if(node.left == null && node.right == null)
{
return ;
}

// When node is internal node
if(!record.containsKey(level))
{
// When adding a new internal node in new level
record.put(level,node.data);
}
else
{
// Update level by internal node
record.put(level,record.get(level) + node.data);
}

internalNodeSum(node.left,record,level+1);
internalNodeSum(node.right,record,level+1);

}

}

public void maxSumInternalNodeByLevel()
{
HashMap<Integer,Integer> record = new HashMap<Integer,Integer>();

this.internalNodeSum(this.root,record,0);

int sum = Integer.MIN_VALUE;

// Find max sum of internal nodes using level
for (int level : record.keySet() )
{
if(sum < record.get(level))
{
// Change max sum
sum = record.get(level);
}
}
// Display calculated result
System.out.println(sum);
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*  Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(-4);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(8);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.right = new TreeNode(9);
tree.root.right.left.right = new TreeNode(2);

/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9

-------------------------------------
Max sum of internal nodes by level is : 15
*/
tree.maxSumInternalNodeByLevel();
}
}``````

#### Output

``15``
``````// Include header file
#include <iostream>
#include <unordered_map>
#include <limits.h>

using namespace std;
// C++ program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
{
public:
// Data value
int data;
// Indicates left and right subtree
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void internalNodeSum(TreeNode *node,
unordered_map < int, int > &record, int level)
{
if (node != NULL)
{
if (node->left == NULL && node->right == NULL)
{
return;
}
// When node is internal node
if (record.find(level) == record.end())
{
// When adding a new internal node in new level
record[level] = node->data;
}
else
{
// Update level by internal node
record[level] = record[level] + node->data;
}
this->internalNodeSum(node->left, record, level + 1);
this->internalNodeSum(node->right, record, level + 1);
}
}
void maxSumInternalNodeByLevel()
{
unordered_map < int, int > record;
this->internalNodeSum(this->root, record, 0);
int sum = INT_MIN;
// Find max sum of internal nodes using level
for (auto &node: record)
{
if (sum < node.second)
{
// Change max sum
sum = node.second;
}
}
// Display calculated result
cout << sum << endl;
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree->root = new TreeNode(1);
tree->root->left = new TreeNode(11);
tree->root->right = new TreeNode(3);
tree->root->right->right = new TreeNode(6);
tree->root->right->right->right = new TreeNode(-4);
tree->root->right->left = new TreeNode(5);
tree->root->left->left = new TreeNode(4);
tree->root->left->left->left = new TreeNode(8);
tree->root->left->left->right = new TreeNode(7);
tree->root->left->left->right->left = new TreeNode(-2);
tree->root->left->left->right->right = new TreeNode(9);
tree->root->right->left->right = new TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree->maxSumInternalNodeByLevel();
return 0;
}``````

#### Output

``15``
``````package main
import "math"
import "fmt"
// Go program for
// Maximum sum of internal nodes among all levels of the given binary tree
type TreeNode struct {
// Data value
data int
// Indicates left and right subtree
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
me.root = nil
return me
}
func(this BinaryTree) internalNodeSum(node * TreeNode,
record map[int] int, level int) {
if node != nil {
if node.left == nil && node.right == nil {
return
}
// When node is internal node
if _, found := record[level] ; !found {
// When adding a new internal node in new level
record[level] = node.data
} else {
// Update level by internal node
record[level] = record[level] + node.data
}
this.internalNodeSum(node.left, record, level + 1)
this.internalNodeSum(node.right, record, level + 1)
}
}
func(this BinaryTree) maxSumInternalNodeByLevel() {
var record = make(map[int] int)
this.internalNodeSum(this.root, record, 0)
var sum int = math.MinInt64
// Find max sum of internal nodes using level
for _, v := range record {
if sum < v{
// Change max sum
sum = v
}
}
// Display calculated result
fmt.Println(sum)
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(11)
tree.root.right = getTreeNode(3)
tree.root.right.right = getTreeNode(6)
tree.root.right.right.right = getTreeNode(-4)
tree.root.right.left = getTreeNode(5)
tree.root.left.left = getTreeNode(4)
tree.root.left.left.left = getTreeNode(8)
tree.root.left.left.right = getTreeNode(7)
tree.root.left.left.right.left = getTreeNode(-2)
tree.root.left.left.right.right = getTreeNode(9)
tree.root.right.left.right = getTreeNode(2)
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree.maxSumInternalNodeByLevel()
}``````

#### Output

``15``
``````// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Maximum sum of internal nodes among all levels of the given binary tree
public class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public void internalNodeSum(TreeNode node,
Dictionary < int, int > record,
int level)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
return;
}
// When node is internal node
if (!record.ContainsKey(level))
{
// When adding a new internal node in new level
}
else
{
// Update level by internal node
record[level] = record[level] + node.data;
}
this.internalNodeSum(node.left, record, level + 1);
this.internalNodeSum(node.right, record, level + 1);
}
}
public void maxSumInternalNodeByLevel()
{
Dictionary < int, int > record = new Dictionary < int, int > ();
this.internalNodeSum(this.root, record, 0);
int sum = int.MinValue;
// Find max sum of internal nodes using level
foreach(KeyValuePair < int, int > level in record)
{
if (sum < level.Value)
{
// Change max sum
sum = level.Value;
}
}
// Display calculated result
Console.WriteLine(sum);
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(-4);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(8);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.right = new TreeNode(9);
tree.root.right.left.right = new TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree.maxSumInternalNodeByLevel();
}
}``````

#### Output

``15``
``````<?php
// Php program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
{
// Data value
public \$data;
// Indicates left and right subtree
public \$left;
public \$right;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
public	function internalNodeSum(\$node, &\$record, \$level)
{
if (\$node != NULL)
{
if (\$node->left == NULL && \$node->right == NULL)
{
return;
}
// When node is internal node
if (!array_key_exists(\$level, \$record))
{
// When adding a new internal node in new level
\$record[\$level] = \$node->data;
}
else
{
// Update level by internal node
\$record[\$level] = \$record[\$level] + \$node->data;
}
\$this->internalNodeSum(\$node->left, \$record, \$level + 1);
\$this->internalNodeSum(\$node->right, \$record, \$level + 1);
}
}
public	function maxSumInternalNodeByLevel()
{
\$record = array();
\$this->internalNodeSum(\$this->root, \$record, 0);
\$sum = -PHP_INT_MAX;
// Find max sum of internal nodes using level
foreach(\$record as \$key => \$value)
{
if (\$sum < \$value)
{
// Change max sum
\$sum = \$value;
}
}
// Display calculated result
echo(\$sum.
"\n");
}
}

function main()
{
\$tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
\$tree->root = new TreeNode(1);
\$tree->root->left = new TreeNode(11);
\$tree->root->right = new TreeNode(3);
\$tree->root->right->right = new TreeNode(6);
\$tree->root->right->right->right = new TreeNode(-4);
\$tree->root->right->left = new TreeNode(5);
\$tree->root->left->left = new TreeNode(4);
\$tree->root->left->left->left = new TreeNode(8);
\$tree->root->left->left->right = new TreeNode(7);
\$tree->root->left->left->right->left = new TreeNode(-2);
\$tree->root->left->left->right->right = new TreeNode(9);
\$tree->root->right->left->right = new TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
\$tree->maxSumInternalNodeByLevel();
}
main();``````

#### Output

``15``
``````// Node JS program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
internalNodeSum(node, record, level)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
return;
}
// When node is internal node
if (!record.has(level))
{
// When adding a new internal node in new level
record.set(level, node.data);
}
else
{
// Update level by internal node
record.set(level, record.get(level) + node.data);
}
this.internalNodeSum(node.left, record, level + 1);
this.internalNodeSum(node.right, record, level + 1);
}
}
maxSumInternalNodeByLevel()
{
var record = new Map();
this.internalNodeSum(this.root, record, 0);
var sum = -Number.MAX_VALUE;
// Find max sum of internal nodes using level
for (let [key, value] of record)
{
if (sum < value)
{
// Change max sum
sum = value;
}
}
// Display calculated result
console.log(sum);
}
}

function main()
{
var tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(-4);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(8);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.right = new TreeNode(9);
tree.root.right.left.right = new TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree.maxSumInternalNodeByLevel();
}
main();``````

#### Output

``15``
``````import sys
#  Python 3 program for
#  Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode :
#  Data value
#  Indicates left and right subtree
def __init__(self, data) :
self.data = data
self.left = None
self.right = None

class BinaryTree :
def __init__(self) :
self.root = None

def internalNodeSum(self, node, record, level) :
if (node != None) :
if (node.left == None and node.right == None) :
return

#  When node is internal node
if ((level not in record.keys())) :
#  When adding a new internal node in new level
record[level] = node.data
else :
#  Update level by internal node
record[level] = record.get(level) + node.data

self.internalNodeSum(node.left, record, level + 1)
self.internalNodeSum(node.right, record, level + 1)

def maxSumInternalNodeByLevel(self) :
record = dict()
self.internalNodeSum(self.root, record, 0)
sum = -sys.maxsize
for key, value in record.items() :
if (sum < value) :
#  Change max sum
sum = value

#  Display calculated result
print(sum)

def main() :
tree = BinaryTree()
#    Binary Tree
#    -----------------------
#          1
#         /  \
#        11   3
#       /    /  \
#      4    5    6
#     / \    \    \
#    8   7    2    -4
#       / \
#     -2   9
tree.root = TreeNode(1)
tree.root.left = TreeNode(11)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(6)
tree.root.right.right.right = TreeNode(-4)
tree.root.right.left = TreeNode(5)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(8)
tree.root.left.left.right = TreeNode(7)
tree.root.left.left.right.left = TreeNode(-2)
tree.root.left.left.right.right = TreeNode(9)
tree.root.right.left.right = TreeNode(2)
#          1          internal node sum [1] = 1
#         /  \
#        11   3       internal node sum [11+3] = 14
#       /    /  \
#      4    5    6    internal node sum [4+5+6] = 15
#     / \    \    \
#    8   7    2   -4  internal node sum [7] = 7
#       / \
#     -2   9
#    -------------------------------------
#    Max sum of internal nodes by level is : 15
tree.maxSumInternalNodeByLevel()

if __name__ == "__main__": main()``````

#### Output

``15``
``````#  Ruby program for
#  Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
#  Data value
#  Indicates left and right subtree
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root
def initialize()
self.root = nil
end

def internalNodeSum(node, record, level)
if (node != nil)
if (node.left == nil && node.right == nil)
return
end

#  When node is internal node
if (!record.key?(level))
#  When adding a new internal node in new level
record[level] = node.data
else

#  Update level by internal node
record[level] = record[level] + node.data
end

self.internalNodeSum(node.left, record, level + 1)
self.internalNodeSum(node.right, record, level + 1)
end

end

def maxSumInternalNodeByLevel()
record = Hash.new()
self.internalNodeSum(self.root, record, 0)
sum = -(2 ** (0. size * 8 - 2))
#  Find max sum of internal nodes using level
record.each { | key, value |
if (sum < value)
#  Change max sum
sum = value
end

}
#  Display calculated result
print(sum, "\n")
end

end

def main()
tree = BinaryTree.new()
#    Binary Tree
#    -----------------------
#          1
#         /  \
#        11   3
#       /    /  \
#      4    5    6
#     / \    \    \
#    8   7    2    -4
#       / \
#     -2   9
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(11)
tree.root.right = TreeNode.new(3)
tree.root.right.right = TreeNode.new(6)
tree.root.right.right.right = TreeNode.new(-4)
tree.root.right.left = TreeNode.new(5)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.left = TreeNode.new(8)
tree.root.left.left.right = TreeNode.new(7)
tree.root.left.left.right.left = TreeNode.new(-2)
tree.root.left.left.right.right = TreeNode.new(9)
tree.root.right.left.right = TreeNode.new(2)
#          1          internal node sum [1] = 1
#         /  \
#        11   3       internal node sum [11+3] = 14
#       /    /  \
#      4    5    6    internal node sum [4+5+6] = 15
#     / \    \    \
#    8   7    2   -4  internal node sum [7] = 7
#       / \
#     -2   9
#    -------------------------------------
#    Max sum of internal nodes by level is : 15
tree.maxSumInternalNodeByLevel()
end

main()``````

#### Output

``````15
``````
``````import scala.collection.mutable._;
// Scala program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode(
// Data value
var data: Int,
// Indicates left and right subtree
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def internalNodeSum(node: TreeNode,
record: HashMap[Int, Int],
level: Int): Unit = {
if (node != null)
{
if (node.left == null && node.right == null)
{
return;
}
// When node is internal node
if (!record.contains(level))
{
// When adding a new internal node in new level
}
else
{
// Update level by internal node
}
internalNodeSum(node.left, record, level + 1);
internalNodeSum(node.right, record, level + 1);
}
}
def maxSumInternalNodeByLevel(): Unit = {
var record: HashMap[Int, Int] = new HashMap[Int, Int]();
this.internalNodeSum(this.root, record, 0);
var sum: Int = Int.MinValue;
// Find max sum of internal nodes using level
for ((_, value) <- record)
{
if (sum < value)
{
// Change max sum
sum = value;
}
}
// Display calculated result
println(sum);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(11);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(-4);
tree.root.right.left = new TreeNode(5);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(8);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.right = new TreeNode(9);
tree.root.right.left.right = new TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree.maxSumInternalNodeByLevel();
}
}``````

#### Output

``15``
``````import Foundation;
// Swift 4 program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func internalNodeSum(_ node: TreeNode? ,
_ record : inout[Int : Int], _ level: Int)
{
if (node  != nil)
{
if (node!.left == nil && node!.right == nil)
{
return;
}
// When node is internal node
if (!record.keys.contains(level))
{
// When adding a new internal node in new level
record[level] = node!.data;
}
else
{
// Update level by internal node
record[level] = record[level]! + node!.data;
}
self.internalNodeSum(node!.left, &record, level + 1);
self.internalNodeSum(node!.right, &record, level + 1);
}
}
func maxSumInternalNodeByLevel()
{
var record: [Int : Int] = [Int : Int]();
self.internalNodeSum(self.root, &record, 0);
var sum: Int = Int.min;
// Find max sum of internal nodes using level
for (_, value) in record
{
if (sum < value)
{
// Change max sum
sum = value;
}
}
// Display calculated result
print(sum);
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(11);
tree.root!.right = TreeNode(3);
tree.root!.right!.right = TreeNode(6);
tree.root!.right!.right!.right = TreeNode(-4);
tree.root!.right!.left = TreeNode(5);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.left = TreeNode(8);
tree.root!.left!.left!.right = TreeNode(7);
tree.root!.left!.left!.right!.left = TreeNode(-2);
tree.root!.left!.left!.right!.right = TreeNode(9);
tree.root!.right!.left!.right = TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree.maxSumInternalNodeByLevel();
}
main();``````

#### Output

``15``
``````// Kotlin program for
// Maximum sum of internal nodes among all levels of the given binary tree
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun internalNodeSum(node: TreeNode ? ,
record : HashMap < Int, Int >  ,
level : Int): Unit
{
if (node != null)
{
if (node.left == null && node.right == null)
{
return;
}
// When node is internal node
if (!record.containsKey(level))
{
// When adding a new internal node in new level
record.put(level, node.data);
}
else
{
// Update level by internal node
record.put(level, record.getValue(level) + node.data);
}
this.internalNodeSum(node.left, record, level + 1);
this.internalNodeSum(node.right, record, level + 1);
}
}
fun maxSumInternalNodeByLevel(): Unit
{
var record: HashMap < Int, Int > = HashMap < Int, Int > ();
this.internalNodeSum(this.root, record, 0);
var sum: Int = Int.MIN_VALUE;
// Find max sum of internal nodes using level
for ((_, value) in record)
{
if (sum < value)
{
// Change max sum
sum = value;
}
}
// Display calculated result
println(sum);
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
11   3
/    /  \
4    5    6
/ \    \    \
8   7    2    -4
/ \
-2   9

*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(11);
tree.root?.right = TreeNode(3);
tree.root?.right?.right = TreeNode(6);
tree.root?.right?.right?.right = TreeNode(-4);
tree.root?.right?.left = TreeNode(5);
tree.root?.left?.left = TreeNode(4);
tree.root?.left?.left?.left = TreeNode(8);
tree.root?.left?.left?.right = TreeNode(7);
tree.root?.left?.left?.right?.left = TreeNode(-2);
tree.root?.left?.left?.right?.right = TreeNode(9);
tree.root?.right?.left?.right = TreeNode(2);
/*

1          internal node sum [1] = 1
/  \
11   3       internal node sum [11+3] = 14
/    /  \
4    5    6    internal node sum [4+5+6] = 15
/ \    \    \
8   7    2   -4  internal node sum [7] = 7
/ \
-2   9
-------------------------------------
Max sum of internal nodes by level is : 15

*/
tree.maxSumInternalNodeByLevel();
}``````

#### Output

``15``

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.