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

Max sum of leaf nodes by level in binary tree

Here given code implementation process.

import java.util.HashMap;
// Java program for
// Maximum sum of leaf 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 int leafNodeSum(TreeNode node, 
                            HashMap < Integer, Integer > record, 
                            int level)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// When node is leaf node
				if (!record.containsKey(level))
				{
					// When adding a new leaf node in new level
					record.put(level, node.data);
				}
				else
				{
					// Update level leaf node sum
					record.put(level, record.get(level) + node.data);
				}
				return record.get(level);
			}
			// Visit left subtree
			int a = leafNodeSum(node.left, record, level + 1);
			// Visit right subtree
			int b = leafNodeSum(node.right, record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	public void maxSumLeafByLevel()
	{
		HashMap < Integer, Integer > record = 
          new HashMap < Integer, Integer > ();
		// Find sum
		int sum = this.leafNodeSum(this.root, record, 0);
		// Display calculated value
		System.out.println(sum);
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*  Binary Tree
		    -----------------------
		          1
		         /  \
		        12   3
		       /    /  \
		      4    5    6
		     / \    \     
		    8   7    2      
		       / \       
		     -2   9    
		*/
		// Add Binary tree nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(12);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		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
		         /  \
		        12   3
		       /    /  \
		      4    5    6   leaf node sum [6] = 6
		     / \    \      
		    8   7    2     leaf node sum [8 + 2] = 10
		       / \       
		     -2   9      leaf node sum [-2 + 9] = 7

		    -------------------------------------
		    Max sum of leaf nodes by level is [8 + 2] : 10
		*/
		tree.maxSumLeafByLevel();
	}
}

Output

10
// Include header file
#include <iostream>

#include <unordered_map>

using namespace std;
// C++ program for
// Maximum sum of leaf 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;
	}
	int leafNodeSum(TreeNode *node, 
                    unordered_map < int, int > &record, int level)
	{
		if (node != NULL)
		{
			if (node->left == NULL && node->right == NULL)
			{
				// When node is leaf node
				if (record.find(level) == record.end())
				{
					// When adding a new leaf node in new level
					record[level] = node->data;
				}
				else
				{
					// Update level leaf node sum
					record[level] = record[level] + node->data;
				}
				return record[level];
			}
			// Visit left subtree
			int a = this->leafNodeSum(node->left, record, level + 1);
			// Visit right subtree
			int b = this->leafNodeSum(node->right, record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	void maxSumLeafByLevel()
	{
		unordered_map < int, int > record;
		// Find sum
		int sum = this->leafNodeSum(this->root, record, 0);
		// Display calculated value
		cout << sum << endl;
	}
};
int main()
{
	BinaryTree *tree = new BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        12   3
	       /    /  \
	      4    5    6
	     / \    \     
	    8   7    2      
	       / \       
	     -2   9    
	*/
	// Add Binary tree nodes
	tree->root = new TreeNode(1);
	tree->root->left = new TreeNode(12);
	tree->root->right = new TreeNode(3);
	tree->root->right->right = new TreeNode(6);
	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
	         /  \
	        12   3
	       /    /  \
	      4    5    6   leaf node sum [6] = 6
	     / \    \      
	    8   7    2     leaf node sum [8 + 2] = 10
	       / \       
	     -2   9      leaf node sum [-2 + 9] = 7
	    -------------------------------------
	    Max sum of leaf nodes by level is [8 + 2] : 10
	*/
	tree->maxSumLeafByLevel();
	return 0;
}

Output

10
package main
import "fmt"
// Go program for
// Maximum sum of leaf 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) leafNodeSum(node * TreeNode, 
                                  record map[int]int, level int) int {
	if node != nil {
		if node.left == nil && node.right == nil {
			// When node is leaf node
			if _, found := record[level] ; !found {
				// When adding a new leaf node in new level
				record[level] = node.data
			} else {
				// Update level leaf node sum
				record[level] = record[level] + node.data
			}
			return record[level]
		}
		// Visit left subtree
		var a int = this.leafNodeSum(node.left, record, level + 1)
		// Visit right subtree
		var b int = this.leafNodeSum(node.right, record, level + 1)
		if a > b {
			return a
		}
		return b
	}
	return 0
}
// Handles the request of finding max sum of level leaf nodes
func(this BinaryTree) maxSumLeafByLevel() {
	var record = make(map[int] int)
	// Find sum
	var sum int = this.leafNodeSum(this.root, record, 0)
	// Display calculated value
	fmt.Println(sum)
}
func main() {
	var tree * BinaryTree = getBinaryTree()
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        12   3
	       /    /  \
	      4    5    6
	     / \    \     
	    8   7    2      
	       / \       
	     -2   9    
	*/
	// Add Binary tree nodes
	tree.root = getTreeNode(1)
	tree.root.left = getTreeNode(12)
	tree.root.right = getTreeNode(3)
	tree.root.right.right = getTreeNode(6)
	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
	         /  \
	        12   3
	       /    /  \
	      4    5    6   leaf node sum [6] = 6
	     / \    \      
	    8   7    2     leaf node sum [8 + 2] = 10
	       / \       
	     -2   9      leaf node sum [-2 + 9] = 7
	    -------------------------------------
	    Max sum of leaf nodes by level is [8 + 2] : 10
	*/
	tree.maxSumLeafByLevel()
}

Output

10
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Maximum sum of leaf 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 int leafNodeSum(TreeNode node, 
                            Dictionary < int, int > record, 
                            int level)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// When node is leaf node
				if (!record.ContainsKey(level))
				{
					// When adding a new leaf node in new level
					record.Add(level, node.data);
				}
				else
				{
					// Update level leaf node sum
					record[level] =  record[level] + node.data;
				}
				return record[level];
			}
			// Visit left subtree
			int a = this.leafNodeSum(node.left, record, level + 1);
			// Visit right subtree
			int b = this.leafNodeSum(node.right, record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	public void maxSumLeafByLevel()
	{
		Dictionary < int, int > record = new Dictionary < int, int > ();
		// Find sum
		int sum = this.leafNodeSum(this.root, record, 0);
		// Display calculated value
		Console.WriteLine(sum);
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		  Binary Tree
		    -----------------------
		          1
		         /  \
		        12   3
		       /    /  \
		      4    5    6
		     / \    \     
		    8   7    2      
		       / \       
		     -2   9    
		*/
		// Add Binary tree nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(12);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		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
		         /  \
		        12   3
		       /    /  \
		      4    5    6   leaf node sum [6] = 6
		     / \    \      
		    8   7    2     leaf node sum [8 + 2] = 10
		       / \       
		     -2   9      leaf node sum [-2 + 9] = 7
		    -------------------------------------
		    Max sum of leaf nodes by level is [8 + 2] : 10
		*/
		tree.maxSumLeafByLevel();
	}
}

Output

10
<?php
// Php program for
// Maximum sum of leaf 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 leafNodeSum($node, &$record, $level)
	{
		if ($node != NULL)
		{
			if ($node->left == NULL && $node->right == NULL)
			{
				// When node is leaf node
				if (!array_key_exists($level, $record))
				{
					// When adding a new leaf node in new level
					$record[$level] = $node->data;
				}
				else
				{
					// Update level leaf node sum
					$record[$level] = $record[$level] + $node->data;
				}
				return $record[$level];
			}
			// Visit left subtree
			$a = $this->leafNodeSum($node->left, $record, $level + 1);
			// Visit right subtree
			$b = $this->leafNodeSum($node->right, $record, $level + 1);
			if ($a > $b)
			{
				return $a;
			}
			return $b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	public	function maxSumLeafByLevel()
	{
		$record = array();
		// Find sum
		$sum = $this->leafNodeSum($this->root, $record, 0);
		// Display calculated value
		echo($sum.
			"\n");
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        12   3
	       /    /  \
	      4    5    6
	     / \    \     
	    8   7    2      
	       / \       
	     -2   9    
	*/
	// Add Binary tree nodes
	$tree->root = new TreeNode(1);
	$tree->root->left = new TreeNode(12);
	$tree->root->right = new TreeNode(3);
	$tree->root->right->right = new TreeNode(6);
	$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
	         /  \
	        12   3
	       /    /  \
	      4    5    6   leaf node sum [6] = 6
	     / \    \      
	    8   7    2     leaf node sum [8 + 2] = 10
	       / \       
	     -2   9      leaf node sum [-2 + 9] = 7
	    -------------------------------------
	    Max sum of leaf nodes by level is [8 + 2] : 10
	*/
	$tree->maxSumLeafByLevel();
}
main();

Output

10
// Node JS program for
// Maximum sum of leaf 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;
	}
	leafNodeSum(node, record, level)
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// When node is leaf node
				if (!record.has(level))
				{
					// When adding a new leaf node in new level
					record.set(level, node.data);
				}
				else
				{
					// Update level leaf node sum
					record.set(level, record.get(level) + node.data);
				}
				return record.get(level);
			}
			// Visit left subtree
			var a = this.leafNodeSum(node.left, record, level + 1);
			// Visit right subtree
			var b = this.leafNodeSum(node.right, record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	maxSumLeafByLevel()
	{
		var record = new Map();
		// Find sum
		var sum = this.leafNodeSum(this.root, record, 0);
		// Display calculated value
		console.log(sum);
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        12   3
	       /    /  \
	      4    5    6
	     / \    \     
	    8   7    2      
	       / \       
	     -2   9    
	*/
	// Add Binary tree nodes
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(12);
	tree.root.right = new TreeNode(3);
	tree.root.right.right = new TreeNode(6);
	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
	         /  \
	        12   3
	       /    /  \
	      4    5    6   leaf node sum [6] = 6
	     / \    \      
	    8   7    2     leaf node sum [8 + 2] = 10
	       / \       
	     -2   9      leaf node sum [-2 + 9] = 7
	    -------------------------------------
	    Max sum of leaf nodes by level is [8 + 2] : 10
	*/
	tree.maxSumLeafByLevel();
}
main();

Output

10
#  Python 3 program for
#  Maximum sum of leaf 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 leafNodeSum(self, node, record, level) :
		if (node != None) :
			if (node.left == None and node.right == None) :
				#  When node is leaf node
				if (not(level in record.keys())) :
					#  When adding a new leaf node in new level
					record[level] = node.data
				else :
					#  Update level leaf node sum
					record[level] = record.get(level) + node.data
				
				return record.get(level)
			
			#  Visit left subtree
			a = self.leafNodeSum(node.left, record, level + 1)
			#  Visit right subtree
			b = self.leafNodeSum(node.right, record, level + 1)
			if (a > b) :
				return a
			
			return b
		
		return 0
	
	#  Handles the request of finding max sum of level leaf nodes
	def maxSumLeafByLevel(self) :
		record = dict()
		#  Find sum
		sum = self.leafNodeSum(self.root, record, 0)
		#  Display calculated value
		print(sum)
	

def main() :
	tree = BinaryTree()
	#  Binary Tree
	#    -----------------------
	#          1
	#         /  \
	#        12   3
	#       /    /  \
	#      4    5    6
	#     / \    \     
	#    8   7    2      
	#       / \       
	#     -2   9    
	#  Add Binary tree nodes
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(12)
	tree.root.right = TreeNode(3)
	tree.root.right.right = TreeNode(6)
	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
	#         /  \
	#        12   3
	#       /    /  \
	#      4    5    6   leaf node sum [6] = 6
	#     / \    \      
	#    8   7    2     leaf node sum [8 + 2] = 10
	#       / \       
	#     -2   9      leaf node sum [-2 + 9] = 7
	#    -------------------------------------
	#    Max sum of leaf nodes by level is [8 + 2] : 10
	tree.maxSumLeafByLevel()

if __name__ == "__main__": main()

Output

10
#  Ruby program for
#  Maximum sum of leaf 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 leafNodeSum(node, record, level) 
		if (node != nil) 
			if (node.left == nil && node.right == nil) 
				#  When node is leaf node
				if (!record.key?(level)) 
					#  When adding a new leaf node in new level
					record[level] = node.data
				else
 
					#  Update level leaf node sum
					record[level] = record[level] + node.data
				end

				return record[level]
			end

			#  Visit left subtree
			a = self.leafNodeSum(node.left, record, level + 1)
			#  Visit right subtree
			b = self.leafNodeSum(node.right, record, level + 1)
			if (a > b) 
				return a
			end

			return b
		end

		return 0
	end

	#  Handles the request of finding max sum of level leaf nodes
	def maxSumLeafByLevel() 
		record = Hash.new()
		#  Find sum
		sum = self.leafNodeSum(self.root, record, 0)
		#  Display calculated value
		print(sum, "\n")
	end

end

def main() 
	tree = BinaryTree.new()
	#  Binary Tree
	#    -----------------------
	#          1
	#         /  \
	#        12   3
	#       /    /  \
	#      4    5    6
	#     / \    \     
	#    8   7    2      
	#       / \       
	#     -2   9    
	#  Add Binary tree nodes
	tree.root = TreeNode.new(1)
	tree.root.left = TreeNode.new(12)
	tree.root.right = TreeNode.new(3)
	tree.root.right.right = TreeNode.new(6)
	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
	#         /  \
	#        12   3
	#       /    /  \
	#      4    5    6   leaf node sum [6] = 6
	#     / \    \      
	#    8   7    2     leaf node sum [8 + 2] = 10
	#       / \       
	#     -2   9      leaf node sum [-2 + 9] = 7
	#    -------------------------------------
	#    Max sum of leaf nodes by level is [8 + 2] : 10
	tree.maxSumLeafByLevel()
end

main()

Output

10
import scala.collection.mutable._;
// Scala program for
// Maximum sum of leaf 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 leafNodeSum(node: TreeNode, 
                    record: HashMap[Int, Int], level: Int): Int = {
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// When node is leaf node
				if (!record.contains(level))
				{
					// When adding a new leaf node in new level
					record.addOne(level, node.data);
				}
				else
				{
					// Update level leaf node sum
					record.addOne(level, record.get(level).get + node.data);
				}
				return record.get(level).get;
			}
			// Visit left subtree
			var a: Int = leafNodeSum(node.left, record, level + 1);
			// Visit right subtree
			var b: Int = leafNodeSum(node.right, record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	def maxSumLeafByLevel(): Unit = {
		var record: HashMap[Int, Int] = new HashMap[Int, Int]();
		// Find sum
		var sum: Int = this.leafNodeSum(this.root, record, 0);
		// Display calculated value
		println(sum);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		  Binary Tree
		    -----------------------
		          1
		         /  \
		        12   3
		       /    /  \
		      4    5    6
		     / \    \     
		    8   7    2      
		       / \       
		     -2   9    
		*/
		// Add Binary tree nodes
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(12);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		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
		         /  \
		        12   3
		       /    /  \
		      4    5    6   leaf node sum [6] = 6
		     / \    \      
		    8   7    2     leaf node sum [8 + 2] = 10
		       / \       
		     -2   9      leaf node sum [-2 + 9] = 7
		    -------------------------------------
		    Max sum of leaf nodes by level is [8 + 2] : 10
		*/
		tree.maxSumLeafByLevel();
	}
}

Output

10
import Foundation;
// Swift 4 program for
// Maximum sum of leaf 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 leafNodeSum(_ node: TreeNode? , 
                     _ record : inout[Int : Int], 
      _ level: Int) -> Int
	{
		if (node  != nil)
		{
			if (node!.left == nil && node!.right == nil)
			{
				// When node is leaf node
				if (!record.keys.contains(level))
				{
					// When adding a new leaf node in new level
					record[level] = node!.data;
				}
				else
				{
					// Update level leaf node sum
					record[level] = record[level]! + node!.data;
				}
				return record[level]!;
			}
			// Visit left subtree
			let a: Int = self.leafNodeSum(node!.left, &record, level + 1);
			// Visit right subtree
			let b: Int = self.leafNodeSum(node!.right, &record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	func maxSumLeafByLevel()
	{
		var record: [Int : Int] = [Int : Int]();
		// Find sum
		let sum: Int = self.leafNodeSum(self.root, &record, 0);
		// Display calculated value
		print(sum);
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        12   3
	       /    /  \
	      4    5    6
	     / \    \     
	    8   7    2      
	       / \       
	     -2   9    
	*/
	// Add Binary tree nodes
	tree.root = TreeNode(1);
	tree.root!.left = TreeNode(12);
	tree.root!.right = TreeNode(3);
	tree.root!.right!.right = TreeNode(6);
	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
	         /  \
	        12   3
	       /    /  \
	      4    5    6   leaf node sum [6] = 6
	     / \    \      
	    8   7    2     leaf node sum [8 + 2] = 10
	       / \       
	     -2   9      leaf node sum [-2 + 9] = 7
	    -------------------------------------
	    Max sum of leaf nodes by level is [8 + 2] : 10
	*/
	tree.maxSumLeafByLevel();
}
main();

Output

10
// Kotlin program for
// Maximum sum of leaf 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 leafNodeSum(node: TreeNode ? , 
                    record : HashMap < Int, Int > , 
                    level : Int): Int
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// When node is leaf node
				if (!record.containsKey(level))
				{
					// When adding a new leaf node in new level
					record.put(level, node.data);
				}
				else
				{
					// Update level leaf node sum
					record.put(level, record.getValue(level) + node.data);
				}
				return record.getValue(level);
			}
			// Visit left subtree
			val a: Int = this.leafNodeSum(node.left, record, level + 1);
			// Visit right subtree
			val b: Int = this.leafNodeSum(node.right, record, level + 1);
			if (a > b)
			{
				return a;
			}
			return b;
		}
		return 0;
	}
	// Handles the request of finding max sum of level leaf nodes
	fun maxSumLeafByLevel(): Unit
	{
		val record: HashMap < Int, Int > = HashMap < Int, Int > ();
		// Find sum
		val sum: Int = this.leafNodeSum(this.root, record, 0);
		// Display calculated value
		println(sum);
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinaryTree = BinaryTree();
	/*
	  Binary Tree
	    -----------------------
	          1
	         /  \
	        12   3
	       /    /  \
	      4    5    6
	     / \    \     
	    8   7    2      
	       / \       
	     -2   9    
	*/
	// Add Binary tree nodes
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(12);
	tree.root?.right = TreeNode(3);
	tree.root?.right?.right = TreeNode(6);
	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
	         /  \
	        12   3
	       /    /  \
	      4    5    6   leaf node sum [6] = 6
	     / \    \      
	    8   7    2     leaf node sum [8 + 2] = 10
	       / \       
	     -2   9      leaf node sum [-2 + 9] = 7
	    -------------------------------------
	    Max sum of leaf nodes by level is [8 + 2] : 10
	*/
	tree.maxSumLeafByLevel();
}

Output

10


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







© 2021, kalkicode.com, All rights reserved