Lexicographically smallest Palindromic Path in a Binary Tree | Java program for the above approach ; Struct binary tree node ; Function to create a new node ; Function to check if the String 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 ; Conbinary tree
import java . util . * ; class GFG { static String finalAns = " " ; static class Node { char data ; Node left , right ; } ; static Node newNode ( char data ) { Node temp = new Node ( ) ; temp . data = data ; temp . left = temp . right = null ; return temp ; } static boolean checkPalindrome ( String s ) { int low = 0 , high = ( int ) s . length ( ) - 1 ; while ( low < high ) { if ( s . charAt ( low ) != s . charAt ( high ) ) return false ; low ++ ; high -- ; } return true ; } static void lexicographicallySmall ( Node root , String s ) { if ( root == null ) return ; s += root . data ; if ( root . left == null && root . right == null ) { if ( checkPalindrome ( s ) ) { if ( finalAns == " $ " ) finalAns = s ; else finalAns = finalAns . compareTo ( s ) <= 0 ? finalAns : s ; } return ; } lexicographicallySmall ( root . left , s ) ; lexicographicallySmall ( root . right , s ) ; } static void getPalindromePath ( Node root ) { finalAns = " $ " ; lexicographicallySmall ( root , " " ) ; if ( finalAns == " $ " ) System . out . print ( " No ▁ Palindromic ▁ Path ▁ exists " ) ; else System . out . print ( finalAns ) ; } public static void main ( String [ ] args ) { Node root = newNode ( ' a ' ) ; root . left = newNode ( ' c ' ) ; root . left . left = newNode ( ' a ' ) ; root . left . right = newNode ( ' g ' ) ; root . right = newNode ( ' b ' ) ; root . right . left = newNode ( ' b ' ) ; root . right . right = newNode ( ' x ' ) ; root . right . left . right = newNode ( ' a ' ) ; getPalindromePath ( root ) ; } }