Maximum sum of longest path from the root to leaf nodes in scala
Scala program for Maximum sum of longest path from the root to leaf nodes. Here mentioned other language solution.
/*
Scala program for
Find the sum of longest path from root to leaf node
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
//set node value
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode,
var height: Int,
var result: Int)
{
def this()
{
this(null, 0, 0);
}
// Find the longest path sum from root to leaf nodes
def findPathSum(node: TreeNode, sum: Int, level: Int): Unit = {
if (node != null)
{
// Recursively calculating the value of
// height and sum of path.
findPathSum(node.left,
sum + node.data, level + 1);
findPathSum(node.right,
sum + node.data, level + 1);
// Check current node is leaf or not
if (node.left == null && node.right == null)
{
// Case When node is leaf
// Check previous calculate height is small or not
if (this.height < level)
{
// When gets a new long height
this.height = level;
this.result = sum + node.data;
}
else if (this.height == level &&
this.result < sum + node.data)
{
// When Two depth are same and new result are larger
this.result = sum + node.data;
}
}
}
}
// Function which is handling the request of
// calculating longest path sum
def longestPathSum(): Unit = {
// Set default value
this.result = Int.MinValue;
this.height = 0;
// Test
findPathSum(this.root, 0, 0);
println("Result : " + this.result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary tree
-----------------------
1
/ \
/ \
/ \
2 5
/ \ / \
1 7 7 2
/ \ \
9 1 -3
/
-7
*/
// Add tree node
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.left.left = new TreeNode(1);
tree.root.left.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(9);
tree.root.right = new TreeNode(5);
tree.root.right.right = new TreeNode(2);
tree.root.right.left = new TreeNode(7);
tree.root.right.left.right = new TreeNode(1);
tree.root.right.left.right.left = new TreeNode(-7);
tree.root.right.right.right = new TreeNode(-3);
tree.longestPathSum();
}
}
Output
Result : 7
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