Find maximum sum, root to leaf path - 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

root leaf path binary tree — Fig 1: Root to leaf paths – Binary tree

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

S. No.	Root to leaf node	Sum of path
1	A -> B -> D	120
2	A -> B -> E	90
3	A -> C -> F	110
4	A -> C -> G	140

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)

max sum binary tree — Fig 2: Root to leaf paths

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]

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

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

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

1.) MaxSumPathRoot2Leaf:

2.) Node Class:

3.) App Class:

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

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

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

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

1.) MaxSumPathRoot2Leaf:

2.) Node Class:

3.) App Class:

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

You may also like: