Maximize sum of path from the Root to a Leaf node in N | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int val ; vector < Node * > child ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> val = key ; return temp ; } void DFS ( Node * root , int sum , int & ans ) { if ( root -> child . size ( ) == 0 ) { ans = max ( ans , sum ) ; return ; } for ( int i = 0 ; i < root -> child . size ( ) ; i ++ ) { DFS ( root -> child [ i ] , sum + root -> child [ i ] -> val , ans ) ; } } Node * root = newNode ( 1 ) ; ( root -> child ) . push_back ( newNode ( 2 ) ) ; ( root -> child ) . push_back ( newNode ( 3 ) ) ; ( root -> child [ 0 ] -> child ) . push_back ( newNode ( 4 ) ) ; ( root -> child [ 1 ] -> child ) . push_back ( newNode ( 6 ) ) ; ( root -> child [ 0 ] -> child ) . push_back ( newNode ( 5 ) ) ; ( root -> child [ 1 ] ) -> child . push_back ( newNode ( 7 ) ) ; ( root -> child [ 1 ] -> child ) . push_back ( newNode ( 8 ) ) ; int maxSumPath = 0 ; DFS ( root , root -> val , maxSumPath ) ; cout << maxSumPath ; return 0 ; }