Queries to check if the path between two nodes in a tree is a palindrome | C # implementation of the approach ; Function that returns true if a palindromic string can be formed using the given characters ; Count odd occurring characters ; Return false if odd count is more than 1 , ; Find to find the Lowest Common Ancestor in the tree ; Base case ; Base case ; Initially value - 1 denotes that we need to find the ancestor ; - 1 denotes that we need to find the lca for x and y , values other than x and y will be the LCA of x and y ; Iterating in the child substree of the currentNode ; Next node that will be checked ; Look for the next child subtree ; Both the nodes exist in the different subtrees , in this case parent node will be the lca ; Handle the cases where LCA is already calculated or both x and y are present in the same subtree ; Function to calculate the character count for each path from node i to 1 ( root node ) ; Updating the character count for each node ; Look for the child subtree ; Function that returns true if a palindromic path is possible between the nodes x and y ; If both x and y are same then lca will be the node itself ; Find the lca of x and y ; Calculating the character count for path node x to y ; Checking if we can form the palindrome string with the all character count ; Function to update character count at node v ; Updating the character count at node v ; Function to perform the queries ; If path can be a palindrome ; Driver Code ; Fill the complete array with 0 ; Edge between 1 and 2 labelled " bbc " ; Edge between 1 and 3 labelled " ac " ; Update the character count from root to the ith node ; Perform the queries
using System ; using System . Collections . Generic ; class GFG { static int MAX_SIZE = 100005 , MAX_CHAR = 26 ; static int [ , ] nodecharsCount = new int [ MAX_SIZE , MAX_CHAR ] ; static List < int > [ ] tree = new List < int > [ MAX_SIZE ] ; static bool canFormPalindrome ( int [ ] charArray ) { int oddCount = 0 ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( charArray [ i ] % 2 == 1 ) oddCount ++ ; } if ( oddCount >= 2 ) return false ; else return true ; } static int LCA ( int currentNode , int x , int y ) { if ( currentNode == x ) return x ; if ( currentNode == y ) return y ; int xLca , yLca ; xLca = yLca = - 1 ; int gotLca = - 1 ; for ( int l = 0 ; l < tree [ currentNode ] . Count ; l ++ ) { int nextNode = tree [ currentNode ] [ l ] ; int out_ = LCA ( nextNode , x , y ) ; if ( out_ == x ) xLca = out_ ; if ( out_ == y ) yLca = out_ ; if ( xLca != - 1 && yLca != - 1 ) return currentNode ; if ( out_ != - 1 ) gotLca = out_ ; } return gotLca ; } static void buildTree ( int i ) { for ( int l = 0 ; l < tree [ i ] . Count ; l ++ ) { int nextNode = tree [ i ] [ l ] ; for ( int j = 0 ; j < MAX_CHAR ; j ++ ) { nodecharsCount [ nextNode , j ] += nodecharsCount [ i , j ] ; } buildTree ( nextNode ) ; } } static bool canFormPalindromicPath ( int x , int y ) { int lcaNode ; if ( x == y ) lcaNode = x ; else lcaNode = LCA ( 1 , x , y ) ; int [ ] charactersCountFromXtoY = new int [ MAX_CHAR ] ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { charactersCountFromXtoY [ i ] = nodecharsCount [ x , i ] + nodecharsCount [ y , i ] - 2 * nodecharsCount [ lcaNode , i ] ; } if ( canFormPalindrome ( charactersCountFromXtoY ) ) return true ; return false ; } static void updateNodecharsCount ( String str , int v ) { for ( int i = 0 ; i < str . Length ; i ++ ) nodecharsCount [ v , str [ i ] - ' a ' ] ++ ; } static void performQueries ( int [ , ] queries , int q ) { int i = 0 ; while ( i < q ) { int x = queries [ i , 0 ] ; int y = queries [ i , 1 ] ; if ( canFormPalindromicPath ( x , y ) ) Console . WriteLine ( " Yes " ) ; else Console . WriteLine ( " No " ) ; i ++ ; } } public static void Main ( String [ ] args ) { for ( int i = 0 ; i < MAX_SIZE ; i ++ ) { for ( int j = 0 ; j < MAX_CHAR ; j ++ ) { nodecharsCount [ i , j ] = 0 ; } } for ( int i = 0 ; i < MAX_SIZE ; i ++ ) { tree [ i ] = new List < int > ( ) ; } tree [ 1 ] . Add ( 2 ) ; updateNodecharsCount ( " bbc " , 2 ) ; tree [ 1 ] . Add ( 3 ) ; updateNodecharsCount ( " ac " , 3 ) ; buildTree ( 1 ) ; int [ , ] queries = { { 1 , 2 } , { 2 , 3 } , { 3 , 1 } , { 3 , 3 } } ; int q = queries . GetLength ( 0 ) ; performQueries ( queries , q ) ; } }