Given a perfect binary tree consisting of N nodes, the task is to check if the number formed by the nodes in any level of the tree forms a palindrome number or not. The root node is not considered to be a palindrome.
Examples:
Input: Tree[][]:
5/ \
3 3
/ \ / \
6 2 3 6
Output: Yes
Explanation: 3 and 3 makes a number 33 which is a palindrome
Input: Tree[][]:
6/ \
3 4
/ \ / \
6 2 1 6
Output: False
Explanation: There is no number formed at any level which is palindrome.
Approach: The task can be solved using a breadth-first search over the tree. Follow the below steps to solve the problem:
- Start traversing the tree from the root node
- From the next level onwards, maintain the number formed by concatenating all the nodes at that level
- Check if it is a palindrome or not
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;struct Node { Node* left; Node* right; int hd; int data;};// Function to create a new nodeNode* newNode(int key){ Node* node = new Node(); node->left = node->right = NULL; node->data = key; return node;}// Function to check if the number is// palindrome or notbool chkp(int n){ string s = to_string(n); string k = s; reverse(s.begin(), s.end()); if (k == s) return true; return false;}// Function to find whether any level// forms a palindromic numberbool chklevel(Node* root){ queue<Node*> q; q.push(root); int k = 1; int p = k; int n = 0; // Using breadth-first-search(bfs) while (!q.empty()) { // if new level start if (p == 0) { // If not the first level if (k != 1) // Checking if the number // at current level // is palindrome if (chkp(n)) { return true; } // Entering new level k *= 2; p = k; n = 0; } Node* t = q.front(); q.pop(); n = n * 10 + t->data; p--; if (t->left) { q.push(t->left); } if (t->right) { q.push(t->right); } } // If number at the last // level is palindrome if (chkp(n)) return true; return false;}// Driver Codeint main(){ // Perfect Binary Tree formation Node* root = newNode(5); root->left = newNode(3); root->right = newNode(3); root->left->left = newNode(6); root->left->right = newNode(2); root->right->right = newNode(6); root->right->left = newNode(3); if (chklevel(root)) cout << "Yes"; else cout << "No";} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static class Node { Node left; Node right; int hd; int data; }; // Function to create a new node static Node newNode(int key) { Node node = new Node(); node.left = node.right = null; node.data = key; return node; } static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a); } // Function to check if the number is // palindrome or not static boolean chkp(int n) { String s = String.valueOf(n); String k = s; s=reverse(s); if (k.equals(s)) return true; return false; } // Function to find whether any level // forms a palindromic number static boolean chklevel(Node root) { Queue<Node> q = new LinkedList<>(); q.add(root); int k = 1; int p = k; int n = 0; // Using breadth-first-search(bfs) while (!q.isEmpty()) { // if new level start if (p == 0) { // If not the first level if (k != 1) // Checking if the number // at current level // is palindrome if (chkp(n)) { return true; } // Entering new level k *= 2; p = k; n = 0; } Node t = q.peek(); q.remove(); n = n * 10 + t.data; p--; if (t.left!=null) { q.add(t.left); } if (t.right!=null) { q.add(t.right); } } // If number at the last // level is palindrome if (chkp(n)) return true; return false; } // Driver Code public static void main(String[] args) { // Perfect Binary Tree formation Node root = newNode(5); root.left = newNode(3); root.right = newNode(3); root.left.left = newNode(6); root.left.right = newNode(2); root.right.right = newNode(6); root.right.left = newNode(3); if (chklevel(root)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approachclass Node: def __init__(self, key): self.left = None self.right = None self.hd = 0 self.data = key# Function to create a node# Function to check if the number is# palindrome or notdef chkp(n): s = str(n) k = s[::-1] if (k == s): return True return False# Function to find whether any level# forms a palindromic numberdef chklevel(root): q = [] q.append(root) k = 1 p = k n = 0 # Using breadth-first-search(bfs) while (len(q) != 0): # if new level start if (p == 0): # If not the first level if (k != 1): # Checking if the number # at current level # is palindrome if (chkp(n)): return True # Entering new level k *= 2 p = k n = 0 t = q[0] q.pop(0) n = n * 10 + t.data p -= 1 if (t.left != None): q.append(t.left) if (t.right != None): q.append(t.right) # If number at the last # level is palindrome if (chkp(n)): return True return False# Driver Code# Perfect Binary Tree formationroot = Node(5)root.left = Node(3)root.right = Node(3)root.left.left = Node(6)root.left.right = Node(2)root.right.right = Node(6)root.right.left = Node(3)if (chklevel(root)): print("Yes")else: print("No")# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ class Node { public Node left; public Node right; public int hd; public int data; }; // Function to create a new node static Node newNode(int key) { Node node = new Node(); node.left = node.right = null; node.data = key; return node; } static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a); } // Function to check if the number is // palindrome or not static bool chkp(int n) { String s = String.Join("",n); String k = s; s=reverse(s); if (k.Equals(s)) return true; return false; } // Function to find whether any level // forms a palindromic number static bool chklevel(Node root) { Queue<Node> q = new Queue<Node>(); q.Enqueue(root); int k = 1; int p = k; int n = 0; // Using breadth-first-search(bfs) while (q.Count!=0) { // if new level start if (p == 0) { // If not the first level if (k != 1) // Checking if the number // at current level // is palindrome if (chkp(n)) { return true; } // Entering new level k *= 2; p = k; n = 0; } Node t = q.Peek(); q.Dequeue(); n = n * 10 + t.data; p--; if (t.left!=null) { q.Enqueue(t.left); } if (t.right!=null) { q.Enqueue(t.right); } } // If number at the last // level is palindrome if (chkp(n)) return true; return false; } // Driver Code public static void Main(String[] args) { // Perfect Binary Tree formation Node root = newNode(5); root.left = newNode(3); root.right = newNode(3); root.left.left = newNode(6); root.left.right = newNode(2); root.right.right = newNode(6); root.right.left = newNode(3); if (chklevel(root)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach class Node { constructor(key) { this.left = null; this.right = null; this.hd = 0; this.data = key; } }; // Function to create a new node // Function to check if the number is // palindrome or not function chkp(n) { let s = (n).toString(); s = s.split(''); let k = [...s]; k = k.join(''); s = s.reverse(); s = s.join('') if (k == s) return true; return false; } // Function to find whether any level // forms a palindromic number function chklevel(root) { let q = []; q.push(root); let k = 1; let p = k; let n = 0; // Using breadth-first-search(bfs) while (q.length != 0) { // if new level start if (p == 0) { // If not the first level if (k != 1) // Checking if the number // at current level // is palindrome if (chkp(n)) { return true; } // Entering new level k *= 2; p = k; n = 0; } let t = q[0]; q.shift(); n = n * 10 + t.data; p--; if (t.left != null) { q.push(t.left); } if (t.right != null) { q.push(t.right); } } // If number at the last // level is palindrome if (chkp(n)) return true; return false; } // Driver Code // Perfect Binary Tree formation let root = new Node(5); root.left = new Node(3); root.right = new Node(3); root.left.left = new Node(6); root.left.right = new Node(2); root.right.right = new Node(6); root.right.left = new Node(3); if (chklevel(root)) document.write("Yes"); else document.write("No"); // This code is contributed by Potta Lokesh </script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
