Skip to main content

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

Max sum of internal nodes by level in 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    
        */
        // Add Binary tree nodes
        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    
	        
	*/
	// Add Binary tree nodes
	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    
	        
	*/
	// Add Binary tree nodes
	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
				record.Add(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 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    
		        
		*/
		// Add Binary tree nodes
		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    
	        
	*/
	// Add Binary tree nodes
	$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    
	        
	*/
	// Add Binary tree nodes
	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    
	#  Add Binary tree nodes
	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_reader :data, :left, :right
	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_reader :root
	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    
	#  Add Binary tree nodes
	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
				record.addOne(level, node.data);
			}
			else
			{
				// Update level by internal node
				record.addOne(level, record.get(level).get + node.data);
			}
			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    
		        
		*/
		// Add Binary tree nodes
		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    
	        
	*/
	// Add Binary tree nodes
	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    
	        
	*/
	// Add Binary tree nodes
	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
Last updated on by Kalkicode




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.

New Comment