Count of 1 's in any path in a Binary Tree | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int data ) { struct Node * newNode = new Node ; newNode -> data = data ; newNode -> left = newNode -> right = NULL ; return ( newNode ) ; } int countUntil ( Node * root , int & res ) { if ( root == NULL ) return 0 ; int l = countUntil ( root -> left , res ) ; int r = countUntil ( root -> right , res ) ; int maxCount ; if ( root -> data == 1 ) maxCount = l + r + 1 ; else maxCount = l + r ; res = max ( res , maxCount ) ; if ( root -> data == 1 ) return max ( l , r ) + 1 ; else return max ( l , r ) ; } int findMaxCount ( Node * root ) { int res = INT_MIN ; countUntil ( root , res ) ; return res ; } int main ( void ) { struct 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 ) ; cout << findMaxCount ( root ) ; return 0 ; }