Lexicographically smallest Palindromic Path in a Binary Tree | Struct binary tree node ; Function to check if the is palindrome or not ; Function to find the lexicographically smallest palindromic path in the Binary Tree ; Base case ; Append current node 's  data to the string ; Check if a node is leaf or not ; Check for the 1 st Palindromic Path ; Store lexicographically the smallest palindromic path ; Recursively traverse left subtree ; Recursively traverse right subtree ; Function to get smallest lexographical palindromic path ; Variable which stores the final result ; Function call to compute lexicographically smallest palindromic Path ; Driver Code ; Construct binary tree
class Node : NEW_LINE INDENT def __init__ ( self , d ) : NEW_LINE INDENT self . data = d NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def checkPalindrome ( s ) : NEW_LINE INDENT low , high = 0 , len ( s ) - 1 NEW_LINE while ( low < high ) : NEW_LINE INDENT if ( s [ low ] != s [ high ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT low += 1 NEW_LINE high -= 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def lexicographicallySmall ( root , s ) : NEW_LINE INDENT global finalAns NEW_LINE if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT s += root . data NEW_LINE if ( not root . left and not root . right ) : NEW_LINE INDENT if ( checkPalindrome ( s ) ) : NEW_LINE INDENT if ( finalAns == " $ " ) : NEW_LINE INDENT finalAns = s NEW_LINE DEDENT else : NEW_LINE INDENT finalAns = min ( finalAns , s ) NEW_LINE DEDENT DEDENT return NEW_LINE DEDENT lexicographicallySmall ( root . left , s ) NEW_LINE lexicographicallySmall ( root . right , s ) NEW_LINE DEDENT def getPalindromePath ( root ) : NEW_LINE INDENT global finalAns NEW_LINE finalAns = " $ " NEW_LINE lexicographicallySmall ( root , " " ) NEW_LINE if ( finalAns == " $ " ) : NEW_LINE INDENT print ( " No ▁ Palindromic ▁ Path ▁ exists " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( finalAns ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT finalAns = " " NEW_LINE root = Node ( ' a ' ) NEW_LINE root . left = Node ( ' c ' ) NEW_LINE root . left . left = Node ( ' a ' ) NEW_LINE root . left . right = Node ( ' g ' ) NEW_LINE root . right = Node ( ' b ' ) NEW_LINE root . right . left = Node ( ' b ' ) NEW_LINE root . right . right = Node ( ' x ' ) NEW_LINE root . right . left . right = Node ( ' a ' ) NEW_LINE getPalindromePath ( root ) NEW_LINE DEDENT