Find the maximum sum leaf to root path in a Binary Tree | GeeksforGeeks
Given a Binary Tree, find the maximum sum path from a leaf to root.
1) First find the leaf node that is on the maximum sum path. In the following code getTargetLeaf() does this by assigning the result to *target_leaf_ref.
2) Once we have the target leaf node, we can print the maximum sum path by traversing the tree. In the following code, printPath() does this.
http://blueocean-penn.blogspot.com/2014/05/find-maximum-sum-from-leaf-to-root-in.html
Also check http://www.geeksforgeeks.org/given-a-binary-tree-print-all-root-to-leaf-paths/
X.
public class MaxSumPathRoot2Leaf { private static int maxSum = 0; private static int[] arr; public static void maxSumPath(Node root, int[] path) { maxSum = Integer.MIN_VALUE; maxSumPathRoot2Leaf(root, path, 0, 0); System.out.println("Maximum Sum :" + maxSum); System.out.println("Root to Leaf Path: " + Arrays.toString(arr)); } public static void maxSumPathRoot2Leaf(Node root, int[] path, int index, int sum) { if (null == root) { return; } path[index++] = root.data; sum += root.data; if (root.left == null && root.right == null) { if (sum > maxSum) { maxSum = sum; arr = Arrays.copyOf(path, index); } return; } maxSumPathRoot2Leaf(root.left, path, index, sum); maxSumPathRoot2Leaf(root.right, path, index, sum); return; }
Read full article from Find the maximum sum leaf to root path in a Binary Tree | GeeksforGeeks
Given a Binary Tree, find the maximum sum path from a leaf to root.
1) First find the leaf node that is on the maximum sum path. In the following code getTargetLeaf() does this by assigning the result to *target_leaf_ref.
2) Once we have the target leaf node, we can print the maximum sum path by traversing the tree. In the following code, printPath() does this.
Time Complexity: Time complexity of the above solution is O(n) as it involves tree traversal two times.
// A utility function that prints all nodes on the path from root to target_leafbool printPath (struct node *root, struct node *target_leaf){ // base case if (root == NULL) return false; // return true if this node is the target_leaf or target leaf is present in // one of its descendants if (root == target_leaf || printPath(root->left, target_leaf) || printPath(root->right, target_leaf) ) { printf("%d ", root->data); return true; } return false;}// This function Sets the target_leaf_ref to refer the leaf node of the maximum // path sum. Also, returns the max_sum using max_sum_refvoid getTargetLeaf (struct node *node, int *max_sum_ref, int curr_sum, struct node **target_leaf_ref){ if (node == NULL) return; // Update current sum to hold sum of nodes on path from root to this node curr_sum = curr_sum + node->data; // If this is a leaf node and path to this node has maximum sum so far, // then make this node target_leaf if (node->left == NULL && node->right == NULL) { if (curr_sum > *max_sum_ref) { *max_sum_ref = curr_sum; *target_leaf_ref = node; } } // If this is not a leaf node, then recur down to find the target_leaf getTargetLeaf (node->left, max_sum_ref, curr_sum, target_leaf_ref); getTargetLeaf (node->right, max_sum_ref, curr_sum, target_leaf_ref);}// Returns the maximum sum and prints the nodes on max sum pathint maxSumPath (struct node *node){ // base case if (node == NULL) return 0; struct node *target_leaf; int max_sum = INT_MIN; // find the target leaf and maximum sum getTargetLeaf (node, &max_sum, 0, &target_leaf); // print the path from root to the target leaf printPath (node, target_leaf); return max_sum; // return maximum sum}
public static int maxSumFromRootHelper(Node root, int sum){
if(root == null)
return sum;
else{
return Math.max(maxSumFromRootHelper(root.left, root.data + sum),
maxSumFromRootHelper(root.right, root.data + sum));
}
}
//store the max sum result
static int max_sum = Integer.MIN_VAL;
//store the leaf
static Node maxNode = null;
public static void findLeaveWithMaxSumFromRoot(Node root, int sum){
if(root == null)
return;
sum = sum + root.data;
if(root.left == null && root.right ==null){
if(sum > max_sum){
max_sum = sum;
maxNode = root;
}
}
else{
findLeaveWithMaxSumFromRoot(root.left, sum);
findLeaveWithMaxSumFromRoot(root.right, sum);
}
} Also check http://www.geeksforgeeks.org/given-a-binary-tree-print-all-root-to-leaf-paths/
/*Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work.*/void printPaths(struct node* node) { int path[1000]; printPathsRecur(node, path, 0);}/* Recursive helper function -- given a node, and an array containing the path from the root node up to but not including this node, print out all the root-leaf paths.*/void printPathsRecur(struct node* node, int path[], int pathLen) { if (node==NULL) return; /* append this node to the path array */ path[pathLen] = node->data; pathLen++; /* it's a leaf, so print the path that led to here */ if (node->left==NULL && node->right==NULL) { printArray(path, pathLen); } else { /* otherwise try both subtrees */ printPathsRecur(node->left, path, pathLen); printPathsRecur(node->right, path, pathLen); }}/* UTILITY FUNCTIONS *//* Utility that prints out an array on a line. */void printArray(int ints[], int len) { int i; for (i=0; i<len; i++) { printf("%d ", ints[i]); } printf("\n");}
public static int maxSum2(final Node node) {
if (node == null) {
return 0;
}
return node.data + Math.max(maxSum2(node.left), maxSum2(node.right));
}
http://www.makeinjava.com/find-maximum-sum-in-root-to-leaf-pa/public class MaxSumPathRoot2Leaf { private static int maxSum = 0; private static int[] arr; public static void maxSumPath(Node root, int[] path) { maxSum = Integer.MIN_VALUE; maxSumPathRoot2Leaf(root, path, 0, 0); System.out.println("Maximum Sum :" + maxSum); System.out.println("Root to Leaf Path: " + Arrays.toString(arr)); } public static void maxSumPathRoot2Leaf(Node root, int[] path, int index, int sum) { if (null == root) { return; } path[index++] = root.data; sum += root.data; if (root.left == null && root.right == null) { if (sum > maxSum) { maxSum = sum; arr = Arrays.copyOf(path, index); } return; } maxSumPathRoot2Leaf(root.left, path, index, sum); maxSumPathRoot2Leaf(root.right, path, index, sum); return; }
Read full article from Find the maximum sum leaf to root path in a Binary Tree | GeeksforGeeks
