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)