I need to find the highest sum path of each node of the following tree. If a nod
ID: 3874941 • Letter: I
Question
I need to find the highest sum path of each node of the following tree. If a node has more tha one child, then every child will have a reference to the first sibling.The problem asks me to return the highest sum path of every node given a number of turns. Cannot repeat a node.
For example: Find the highest sum path of the root node with a maximum of 4 turns.
So it would go something like 20 + 50 + 42 + 14
Any help to implement this algorithim in java would be appreciated.
(20 ( 50 42 ) 42 14)+( 5 ) (8) 10 60Explanation / Answer
class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int data) {
this.data = data;
left = right = null;
}
}
class Result {
public int val;
}
class BinaryTree {
// Root of the Binary Tree
Node root;
int findMaxUtil(TreeNode node, Result res)
{
if (node == null)
return 0;
int l = findMaxUtil(node.left, res);
int r = findMaxUtil(node.right, res);
int max_single = Math.max(Math.max(l, r) + node.data, node.data);
int max_top = Math.max(max_single, l + r + node.data);
// Store the Maximum Result.
res.val = Math.max(res.val, max_top);
return max_single;
}
int findMaxSum() {
return findMaxSum(root);
}
int findMaxSum(TreeNode node) {
// Initialize result
Result res = new Result();
res.val = Integer.MIN_VALUE;
// Compute and return result
findMaxUtil(node, res);
return res.val;
}
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(42);
tree.root.right = new Node(50);
tree.root.left.left = new Node(14);
tree.root.left.left.right = new Node(5)
tree.root.left.right = new Node(8);
tree.root.right.right = new Node(5);
tree.root.right.left = new Node(42);
tree.root.right.left.left = new Node(10);
tree.root.right.left.left.right = new Node(60);
System.out.println("maximum path sum is : " + tree.findMaxSum());
}
}