Count of subtrees in a Binary Tree having XOR value K | C ++ program to find the count of subtrees in a Binary Tree having XOR value K ; A binary tree node ; A utility function to allocate a new node ; Base Case : If node is NULL , return 0 ; Calculating the XOR of the current subtree ; Increment res if xr is equal to k ; Return the XOR value of the current subtree ; Function to find the required count ; Initialize result variable ' res ' ; Recursively traverse the tree and compute the count ; return the count ' res ' ; Driver program ; Create the binary tree by adding nodes to it
#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 rec ( Node * root , int & res , int & k ) { if ( root == NULL ) { return 0 ; } int xr = root -> data ; xr ^= rec ( root -> left , res , k ) ; xr ^= rec ( root -> right , res , k ) ; if ( xr == k ) { res ++ ; } return xr ; } int findCount ( Node * root , int K ) { int res = 0 ; rec ( root , res , K ) ; return res ; } int main ( void ) { struct Node * root = newNode ( 2 ) ; root -> left = newNode ( 1 ) ; root -> right = newNode ( 9 ) ; root -> left -> left = newNode ( 10 ) ; root -> left -> right = newNode ( 5 ) ; int K = 5 ; cout << findCount ( root , K ) ; return 0 ; }