Lexicographically smallest Palindromic Path in a Binary Tree | C ++ 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 ; Construct binary tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { char data ; Node * left , * right ; } ; Node * newNode ( char data ) { Node * temp = new Node ( ) ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } bool checkPalindrome ( string s ) { int low = 0 , high = ( int ) s . size ( ) - 1 ; while ( low < high ) { if ( s [ low ] != s [ high ] ) return false ; low ++ ; high -- ; } return true ; } void lexicographicallySmall ( Node * root , string s , string & finalAns ) { if ( root == NULL ) return ; s += root -> data ; if ( ! root -> left and ! root -> right ) { if ( checkPalindrome ( s ) ) { if ( finalAns == " $ " ) finalAns = s ; else finalAns = min ( finalAns , s ) ; } return ; } lexicographicallySmall ( root -> left , s , finalAns ) ; lexicographicallySmall ( root -> right , s , finalAns ) ; } void getPalindromePath ( Node * root ) { string finalAns = " $ " ; lexicographicallySmall ( root , " " , finalAns ) ; if ( finalAns == " $ " ) cout << " No ▁ Palindromic ▁ Path ▁ exists " ; else cout << finalAns ; } int main ( ) { 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 ) ; return 0 ; }