Maximize sum of path from the Root to a Leaf node in N | Java program for the above approach ; Stores the maximum sum of a path ; Structure of a node in the tree ; Utility function to create a new node in the tree ; Recursive function to calculate the maximum sum in a path using DFS ; If current node is a leaf node ; Traversing all children of the current node ; Recursive call for all the children nodes ; Given Generic Tree ; Function Call
import java . util . * ; public class Main { static int maxSumPath = 0 ; static class Node { public int val ; public Vector < Node > child ; public Node ( int key ) { val = key ; child = new Vector < Node > ( ) ; } } static Node newNode ( int key ) { Node temp = new Node ( key ) ; return temp ; } static void DFS ( Node root , int sum ) { if ( root . child . size ( ) == 0 ) { maxSumPath = Math . max ( maxSumPath , sum ) ; return ; } for ( int i = 0 ; i < root . child . size ( ) ; i ++ ) { DFS ( root . child . get ( i ) , sum + root . child . get ( i ) . val ) ; } } public static void main ( String [ ] args ) { Node root = newNode ( 1 ) ; ( root . child ) . add ( newNode ( 2 ) ) ; ( root . child ) . add ( newNode ( 3 ) ) ; ( root . child . get ( 0 ) . child ) . add ( newNode ( 4 ) ) ; ( root . child . get ( 1 ) . child ) . add ( newNode ( 6 ) ) ; ( root . child . get ( 0 ) . child ) . add ( newNode ( 5 ) ) ; ( root . child . get ( 1 ) ) . child . add ( newNode ( 7 ) ) ; ( root . child . get ( 1 ) . child ) . add ( newNode ( 8 ) ) ; DFS ( root , root . val ) ; System . out . print ( maxSumPath ) ; } }