Count of 1 's in any path in a Binary Tree | A binary tree node ; A utility function to allocate a new node ; This function updates overall count of 1 in ' res ' And returns count 1 s going through root . ; Base Case ; l and r store count of 1 s going through left and right child of root respectively ; maxCount represents the count of 1 s when the Node under consideration is the root of the maxCount path and no ancestors of the root are there in maxCount path ; if the value at node is 1 then its count will be considered including the leftCount and the rightCount ; Store the Maximum Result . ; if the value at node is 1 then its count will be considered including the maximum of leftCount or the rightCount ; Returns maximum count of 1 in any path in tree with given root ; Initialize result ; Compute and return result ; Driver program
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT newNode = Node ( ) NEW_LINE newNode . data = data NEW_LINE newNode . left = newNode . right = None NEW_LINE return ( newNode ) NEW_LINE DEDENT res = 0 NEW_LINE def countUntil ( root ) : NEW_LINE INDENT global res NEW_LINE if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT l = countUntil ( root . left ) NEW_LINE r = countUntil ( root . right ) NEW_LINE maxCount = 0 NEW_LINE if ( root . data == 1 ) : NEW_LINE INDENT maxCount = l + r + 1 NEW_LINE DEDENT else : NEW_LINE INDENT maxCount = l + r NEW_LINE DEDENT res = max ( res , maxCount ) NEW_LINE if ( root . data == 1 ) : NEW_LINE INDENT return max ( l , r ) + 1 NEW_LINE DEDENT else : NEW_LINE INDENT return max ( l , r ) NEW_LINE DEDENT DEDENT def findMaxCount ( root ) : NEW_LINE INDENT global res NEW_LINE res = - 999999 NEW_LINE countUntil ( root ) NEW_LINE return res NEW_LINE DEDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 0 ) NEW_LINE root . right = newNode ( 1 ) NEW_LINE root . left . left = newNode ( 1 ) NEW_LINE root . left . right = newNode ( 1 ) NEW_LINE root . left . right . left = newNode ( 1 ) NEW_LINE root . left . right . right = newNode ( 0 ) NEW_LINE print ( findMaxCount ( root ) ) NEW_LINE