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 { constructor ( ) { this . left = null ; this . data = 0 ; this . right = null ; } } ; var res = 0 ; function newNode ( data ) { var newNode = new Node ( ) ; newNode . data = data ; newNode . left = newNode . right = null ; return ( newNode ) ; } function countUntil ( root ) { if ( root == null ) return 0 ; var l = countUntil ( root . left ) ; var r = countUntil ( root . right ) ; var maxCount ; if ( root . data == 1 ) maxCount = l + r + 1 ; else maxCount = l + r ; res = Math . max ( res , maxCount ) ; if ( root . data == 1 ) return Math . max ( l , r ) + 1 ; else return Math . max ( l , r ) ; } function findMaxCount ( root ) { res = - 1000000000 ; countUntil ( root ) ; return res ; } var root = newNode ( 1 ) ; root . left = newNode ( 0 ) ; root . right = newNode ( 1 ) ; root . left . left = newNode ( 1 ) ; root . left . right = newNode ( 1 ) ; root . left . right . left = newNode ( 1 ) ; root . left . right . right = newNode ( 0 ) ; document . write ( findMaxCount ( root ) ) ;