Maximize sum of path from the Root to a Leaf node in N | 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
maxSumPath = 0 NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . val = key NEW_LINE self . child = [ ] NEW_LINE DEDENT DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( key ) NEW_LINE return temp NEW_LINE DEDENT def DFS ( root , Sum ) : NEW_LINE INDENT global maxSumPath NEW_LINE if ( len ( root . child ) == 0 ) : NEW_LINE INDENT maxSumPath = max ( maxSumPath , Sum ) NEW_LINE return NEW_LINE DEDENT for i in range ( len ( root . child ) ) : NEW_LINE INDENT DFS ( root . child [ i ] , Sum + root . child [ i ] . val ) NEW_LINE DEDENT DEDENT root = newNode ( 1 ) NEW_LINE ( root . child ) . append ( newNode ( 2 ) ) NEW_LINE ( root . child ) . append ( newNode ( 3 ) ) NEW_LINE ( root . child [ 0 ] . child ) . append ( newNode ( 4 ) ) NEW_LINE ( root . child [ 1 ] . child ) . append ( newNode ( 6 ) ) NEW_LINE ( root . child [ 0 ] . child ) . append ( newNode ( 5 ) ) NEW_LINE ( root . child [ 1 ] ) . child . append ( newNode ( 7 ) ) NEW_LINE ( root . child [ 1 ] . child ) . append ( newNode ( 8 ) ) NEW_LINE DFS ( root , root . val ) NEW_LINE print ( maxSumPath ) NEW_LINE