Find maximum sum, root to leaf path in binary tree (Java/ recursive/ example)

• Given a binary tree, find maximum sum from root to leaf paths using recursive algorithm.
  • Traverse binary tree using preOrder depth first search (DFS) algorithm.
• Binary tree is rooted at node A and containing four leaf nodes. (Refer Fig 1)
  • So, there exists four paths, from root to leaf nodes.
• Find sum of all nodes in each path, from root to leaf nodes.
  • Print maximum sum path (among all root to leaf paths).
• We have already discussed similar problem:
  • Print all paths from root to leaf nodes in a binary tree.
  • Find root to leaf path,sum equals given number in a binary tree

The root to leaf paths in a binary tree are as follows:

So, clearly the path A -> C -> G  has maximum sum of 140, which is expected output of our problem.

Algorithm: find maximum sum, root to leaf path in a binary tree

• Declare maxSum variable for maximum sum from root to leaf path.
• Array arr containing the root to leaf path, having maximum sum
• Perform pre order traversal, Save current node value in arr
  • Calculate the sum from root to leaf for current traversal
  • Keep on performing the traversal till we encounter the leaf
    • If we reach the leaf node
      • Check the sum of root to leaf path is greater than maxSum
        • If yes, Update the maxSum and
          • Save the path in arr
      • If no, lets move on (this not the maximum sum path)
  • Perform the traversal for left & right subtree.
• At the end of traversal, we will get:
  • maxSum  and arr containing max sum path (root to leaf node).
• Time Complexity: O(n)

Program – find maximum sum, root to leaf path in binary tree ( Java)

1.) MaxSumPathRoot2Leaf:

• MaxSumPathRoot2Leaf class is responsible for printing maximum sum path, from root to leaf node.
• Traverse the binary tree using recursive algorithm.

package org.learn.Question;

import java.util.Arrays;

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;
 }
}

2.) Node Class:

• Node class is representing the nodes of binary tree.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are constructing the binary tree in a main method.
• We are calling method of MaxSumPathRoot2Leaf class, to print max sum path from root to leaf node.

package org.learn.Client;

import org.learn.Question.MaxSumPathRoot2Leaf;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  Node root = Node.createNode(50);
  root.left = Node.createNode(30);
  root.right = Node.createNode(30);
  // left sub tree
  root.left.left = Node.createNode(40);
  root.left.right = Node.createNode(10);

  // right subtree
  root.right.left = Node.createNode(30);
  root.right.right = Node.createNode(60);

  int[] path = new int[512];
  MaxSumPathRoot2Leaf.maxSumPath(root, path);
 }
}

Output – maximum sum, root to leaf path in a binary tree (java)

Maximum Sum :140
Root to Leaf Path: [50, 30, 60]

Download code-maximum sum, root to leaf path(binary tree)