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 None , 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
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT newNode = Node ( data ) NEW_LINE return newNode NEW_LINE DEDENT def rec ( root , res , k ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return [ 0 , res ] ; NEW_LINE DEDENT xr = root . data ; NEW_LINE tmp , res = rec ( root . left , res , k ) ; NEW_LINE xr ^= tmp NEW_LINE tmp , res = rec ( root . right , res , k ) ; NEW_LINE xr ^= tmp NEW_LINE if ( xr == k ) : NEW_LINE INDENT res += 1 NEW_LINE DEDENT return xr , res ; NEW_LINE DEDENT def findCount ( root , K ) : NEW_LINE ' NEW_LINE INDENT res = 0 ; NEW_LINE tmp , res = rec ( root , res , K ) ; NEW_LINE DEDENT ' NEW_LINE INDENT return res ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 2 ) ; NEW_LINE root . left = newNode ( 1 ) ; NEW_LINE root . right = newNode ( 9 ) ; NEW_LINE root . left . left = newNode ( 10 ) ; NEW_LINE root . left . right = newNode ( 5 ) ; NEW_LINE K = 5 ; NEW_LINE print ( findCount ( root , K ) ) NEW_LINE DEDENT