Given a Binary Tree with each node representing an alphabet, the task is to find lexicographically smallest palindromic root to leaf path. If no palindromic path exists, print “No Palindromic Path exists”.
Examples:
Input:
a
/ \
c b
/ \ / \
a g b x
\
a
Output:
abba
Explanation:
There were total 4 root to leaf paths out of which 2 paths(i.e., “aca” and “abba”) were palindromic paths but as “abba” is lexicographically smaller, print “abba” as output.Input:
a
/ \
z k
/ \ / \
s e k u
\
e
Output:
No Palindromic Path exists
Approach: Follow the steps to solve the problem
- The main idea is to use Preorder Traversal
- Traverse the tree in Preorder fashion.
- Keep storing the node values in a string.
- As soon as a leaf node is reached, check if the string formed from a root to leaf path is a palindrome or not.
- If it’s a palindrome store it in a variable only if it’s lexicographically the smallest palindromic path.
- Print the palindrome, if it exists.
Below is the implementation of the above approach:
C++
// C++ program// for the above approach#include <bits/stdc++.h>using namespace std;// Struct binary tree nodestruct Node { char data; Node *left, *right;};// Function to create a new nodeNode* newNode(char data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to check if the// string is palindrome or notbool 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;}// Function to find the lexicographically// smallest palindromic path in the Binary Treevoid lexicographicallySmall(Node* root, string s, string& finalAns){ // Base case if (root == NULL) return; // Append current node's // data to the string s += root->data; // Check if a node is leaf or not if (!root->left and !root->right) { if (checkPalindrome(s)) { // Check for the 1st // Palindromic Path if (finalAns == "$") finalAns = s; // Store lexicographically the // smallest palindromic path else finalAns = min(finalAns, s); } return; } // Recursively traverse left subtree lexicographicallySmall(root->left, s, finalAns); // Recursively traverse right subtree lexicographicallySmall(root->right, s, finalAns);}// Function to get smallest// lexicographical palindromic// pathvoid getPalindromePath(Node* root){ // Variable which stores // the final result string finalAns = "$"; // Function call to compute // lexicographically smallest // palindromic Path lexicographicallySmall(root, "", finalAns); if (finalAns == "$") cout << "No Palindromic Path exists"; else cout << finalAns;}// Driver Codeint main(){ // Construct binary tree 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;} |
Java
// Java program// for the above approachimport java.util.*;class GFG{static String finalAns=""; // Struct binary tree nodestatic class Node{ char data; Node left, right;};// Function to create a new nodestatic Node newNode(char data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check if the// String is palindrome or notstatic 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;}// Function to find the lexicographically// smallest palindromic path in the Binary Treestatic void lexicographicallySmall(Node root, String s){ // Base case if (root == null) return; // Append current node's // data to the String s += root.data; // Check if a node is leaf or not if (root.left == null && root.right == null) { if (checkPalindrome(s)) { // Check for the 1st // Palindromic Path if (finalAns == "$") finalAns = s; // Store lexicographically the // smallest palindromic path else finalAns = finalAns.compareTo(s) <= 0 ? finalAns:s; } return; } // Recursively traverse left subtree lexicographicallySmall(root.left, s); // Recursively traverse right subtree lexicographicallySmall(root.right, s);}// Function to get smallest// lexicographical palindromic// pathstatic void getPalindromePath(Node root){ // Variable which stores // the final result finalAns = "$"; // Function call to compute // lexicographically smallest // palindromic Path lexicographicallySmall(root, ""); if (finalAns == "$") System.out.print("No Palindromic Path exists"); else System.out.print(finalAns);} // Driver Codepublic static void main(String[] args){ // Construct binary tree 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);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program# for the above approach# Struct binary tree nodeclass Node: def __init__(self, d): self.data = d self.left = None self.right = None# Function to check if the# is palindrome or notdef checkPalindrome(s): low, high = 0, len(s) - 1 while (low < high): if (s[low] != s[high]): return False low += 1 high -= 1 return True# Function to find the lexicographically# smallest palindromic path in the Binary Treedef lexicographicallySmall(root, s): global finalAns # Base case if (root == None): return # Append current node's # data to the string s += root.data # Check if a node is leaf or not if (not root.left and not root.right): if (checkPalindrome(s)): # Check for the 1st # Palindromic Path if (finalAns == "$"): finalAns = s # Store lexicographically the # smallest palindromic path else: finalAns = min(finalAns, s) return # Recursively traverse left subtree lexicographicallySmall(root.left, s) # Recursively traverse right subtree lexicographicallySmall(root.right, s)# Function to get smallest# lexicographical palindromic# pathdef getPalindromePath(root): global finalAns # Variable which stores # the final result finalAns = "$" # Function call to compute # lexicographically smallest # palindromic Path lexicographicallySmall(root, "") if (finalAns == "$"): print("No Palindromic Path exists") else: print(finalAns) # Driver Codeif __name__ == '__main__': finalAns = "" # Construct binary tree root = Node('a') root.left = Node('c') root.left.left = Node('a') root.left.right = Node('g') root.right = Node('b') root.right.left = Node('b') root.right.right = Node('x') root.right.left.right = Node('a') getPalindromePath(root) # This code is contributed by mohit kumar 29. |
C#
// C# program// for the above approachusing System;public class GFG{static String finalAns = ""; // Struct binary tree nodeclass Node{ public char data; public Node left, right;};// Function to create a new nodestatic Node newNode(char data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check if the// String is palindrome or notstatic bool checkPalindrome(String s){ int low = 0, high = (int)s.Length - 1; while (low < high) { if (s[low] != s[high]) return false; low++; high--; } return true;}// Function to find the lexicographically// smallest palindromic path in the Binary Treestatic void lexicographicallySmall(Node root, String s){ // Base case if (root == null) return; // Append current node's // data to the String s += root.data; // Check if a node is leaf or not if (root.left == null && root.right == null) { if (checkPalindrome(s)) { // Check for the 1st // Palindromic Path if (finalAns == "$") finalAns = s; // Store lexicographically the // smallest palindromic path else finalAns = finalAns.CompareTo(s) <= 0 ? finalAns:s; } return; } // Recursively traverse left subtree lexicographicallySmall(root.left, s); // Recursively traverse right subtree lexicographicallySmall(root.right, s);}// Function to get smallest// lexicographical palindromic// pathstatic void getPalindromePath(Node root){ // Variable which stores // the readonly result finalAns = "$"; // Function call to compute // lexicographically smallest // palindromic Path lexicographicallySmall(root, ""); if (finalAns == "$") Console.Write("No Palindromic Path exists"); else Console.Write(finalAns);} // Driver Codepublic static void Main(String[] args){ // Construct binary tree 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);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach let finalAns=""; // Struct binary tree node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to create a new node function newNode(data) { let temp = new Node(data); return temp; } // Function to check if the // String is palindrome or not function checkPalindrome(s) { let low = 0, high = s.length - 1; while (low < high) { if (s[low] != s[high]) return false; low++; high--; } return true; } // Function to find the lexicographically // smallest palindromic path in the Binary Tree function lexicographicallySmall(root, s) { // Base case if (root == null) return; // Append current node's // data to the String s += root.data; // Check if a node is leaf or not if (root.left == null && root.right == null) { if (checkPalindrome(s)) { // Check for the 1st // Palindromic Path if (finalAns == "$") finalAns = s; // Store lexicographically the // smallest palindromic path else finalAns = finalAns.localeCompare(s) <= 0 ? finalAns:s; } return; } // Recursively traverse left subtree lexicographicallySmall(root.left, s); // Recursively traverse right subtree lexicographicallySmall(root.right, s); } // Function to get smallest // lexicographical palindromic // path function getPalindromePath(root) { // Variable which stores // the final result finalAns = "$"; // Function call to compute // lexicographically smallest // palindromic Path lexicographicallySmall(root, ""); if (finalAns == "$") document.write("No Palindromic Path exists"); else document.write(finalAns); } // Construct binary tree let 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);// This code is contributed by suresh07.</script> |
Output:
abba
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
