Given a binary tree, find out the maximum sum of value from root to each leaf.

by

Objective: – Find the maximum sum leaf to root path in a Binary Tree. Means in all the paths from root to leaves, find the path which has the maximum sum.

Input: A binary tree

Example:

Maximum Sum Leaf to Root pathApproach:

This solution will be divided into two parts

Find the leaf which has the maximum sum from root.

  • Take a global variable maxLeaf and maxSum. (this maxLeaf will the node which has the maximum sum path and maxSum will the maximum sum.)
  • Do the preorder traversal
  • At each node, maintain a another variable sum = sum + root.data.
  • When ever you reach to any leaf, check if sum>maxSum, if yes then update the maxLeaf and maxSum.

Print the path from root to that leaf.

Please refer this link to print the path.

Complete Code:


public class MaxSumLeafToRoot {
static int maxSum = Integer.MIN_VALUE;
static Node maxLeaf=null;
static int currentSum =0;
public void maxSum(Node root, int sum){
if(root!=null){
sum=sum+root.data;
if(sum>maxSum && root.left==null && root.right==null){
maxLeaf = root;
maxSum = sum;
}
// System.out.println("Sum " + sum);
maxSum(root.left,sum);
maxSum(root.right,sum);
}
}
public Boolean path(Node root, Node leaf){
if(root==null) return false;
if ((root == leaf) || path(root.left, leaf) ||path(root.right, leaf) )
{
System.out.print(" " + root.data);
return true;
}
return false;
}
public static void main (String[] args) throws java.lang.Exception
{
Node root = new Node(1);
root.left = new Node (2);
root.right = new Node (3);
root.left.left = new Node (4);
root.left.right = new Node (5);
root.right.left = new Node (6);
root.right.left.left = new Node (8);
MaxSumLeafToRoot i = new MaxSumLeafToRoot();
i.maxSum(root,0);
System.out.println("Maximum Sum Leaf to Root path " + maxSum);
System.out.print("Path :");
i.path(root,maxLeaf);
}
}
class Node{
int data;
Node left;
Node right;
public Node (int data){
this.data = data;
left = null;
right = null;
}
}

view raw

MaxSumLeafToRoot.java

hosted with ❤ by GitHub

Output:

Maximum Sum Leaf to Root path :18
Path : 8 6 3 1

Related Posts: