Count of 1 's in any path in a Binary Tree | Java implementation of the above approach ; 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 GFG { static class Node { int data ; Node left , right ; } ; static int res ; static Node newNode ( int data ) { Node newNode = new Node ( ) ; newNode . data = data ; newNode . left = newNode . right = null ; return ( newNode ) ; } static int countUntil ( Node root ) { if ( root == null ) return 0 ; int l = countUntil ( root . left ) ; int r = countUntil ( root . right ) ; int 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 ) ; } static int findMaxCount ( Node root ) { res = Integer . MIN_VALUE ; countUntil ( root ) ; return res ; } public static void main ( String [ ] args ) { Node 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 ) ; System . out . print ( findMaxCount ( root ) ) ; } }