Given a binary tree and the task if to check if it’s level order traversal results in a palindrome or not.
Examples:
Input:
Output: Yes
RADAR is the level order traversal of the
given tree which is a palindrome.
Input:
Output: No
Approach:
- Traverse the Binary Tree in level order and store the nodes in a stack.
- Traverse the Binary Tree in level order once again and compare the data in the node with the data at top of stack.
- In case there is a match, move on to the next node.
- In case there is a mismatch, stop and print No.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure for a node of the treestruct node { char data; node *left, *right;};// Function to add a node// to the Binary Treenode* add(char data){ node* newnode = new node; newnode->data = data; newnode->left = newnode->right = NULL; return newnode;}// Function to perform level order traversal// of the Binary Tree and add the nodes to// the stackvoid findInv(node* root, stack<node*>& S){ if (root == NULL) return; // The queue holds the nodes which are being // processed starting from the root queue<node*> Q; Q.push(root); while (Q.size()) { node* temp = Q.front(); Q.pop(); // Take the node out of the Queue // and push it to the stack S.push(temp); // If there is a left child // then push it to the queue if (temp->left != NULL) Q.push(temp->left); // If there is a right child // then push it to the queue if (temp->right != NULL) Q.push(temp->right); }}// Function that returns true if the// level order traversal of the// tree results in a palindromebool isPalindrome(stack<node*> S, node* root){ queue<node*> Q; Q.push(root); while (Q.size()) { // To store the element at // the front of the queue node* temp = Q.front(); // To store the element at // the top of the stack node* temp1 = S.top(); S.pop(); Q.pop(); // If the data in the node at the top // of stack does not match the data // in the node at the front of the queue if (temp->data != temp1->data) return false; if (temp->left != NULL) Q.push(temp->left); if (temp->right != NULL) Q.push(temp->right); } // If there is no mismatch return true;}// Driver codeint main(){ // Creating the binary tree node* root = add('R'); root->left = add('A'); root->right = add('D'); root->left->left = add('A'); root->left->right = add('R'); // Stack to store the nodes of the // tree in level order traversal stack<node*> S; findInv(root, S); // If the level order traversal // results in a palindrome if (isPalindrome(S, root)) cout << "Yes"; else cout << "NO"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Structure for a node of the treestatic class node{ char data; node left, right;};// Function to add a node// to the Binary Treestatic node add(char data){ node newnode = new node(); newnode.data = data; newnode.left = newnode.right = null; return newnode;}// Function to perform level order traversal// of the Binary Tree and add the nodes to// the stackstatic void findInv(node root, Stack<node> S){ if (root == null) return; // The queue holds the nodes which are being // processed starting from the root Queue<node> Q = new LinkedList<>(); Q.add(root); while (Q.size() > 0) { node temp = Q.peek(); Q.remove(); // Take the node out of the Queue // and push it to the stack S.add(temp); // If there is a left child // then push it to the queue if (temp.left != null) Q.add(temp.left); // If there is a right child // then push it to the queue if (temp.right != null) Q.add(temp.right); }}// Function that returns true if the// level order traversal of the// tree results in a palindromestatic boolean isPalindrome(Stack<node> S, node root){ Queue<node> Q = new LinkedList<>(); Q.add(root); while (Q.size() > 0) { // To store the element at // the front of the queue node temp = Q.peek(); // To store the element at // the top of the stack node temp1 = S.peek(); S.pop(); Q.remove(); // If the data in the node at the top // of stack does not match the data // in the node at the front of the queue if (temp.data != temp1.data) return false; if (temp.left != null) Q.add(temp.left); if (temp.right != null) Q.add(temp.right); } // If there is no mismatch return true;}// Driver codepublic static void main(String[] args){ // Creating the binary tree node root = add('R'); root.left = add('A'); root.right = add('D'); root.left.left = add('A'); root.left.right = add('R'); // Stack to store the nodes of the // tree in level order traversal Stack<node> S = new Stack<node>(); findInv(root, S); // If the level order traversal // results in a palindrome if (isPalindrome(S, root)) System.out.print("Yes"); else System.out.print("NO");}}// This code is contributed by 29AjayKumar |
Python3
# Python implementation of the approach# Linked List node class Node: def __init__(self, data): self.info = data self.left = None self.right = None# Function to append a node# to the Binary Treedef append(data): newnode = Node(0) newnode.data = data newnode.left = newnode.right = None return newnode# Function to perform level order traversal# of the Binary Tree and append the nodes to# the stackdef findInv(root, S): if (root == None): return # The queue holds the nodes which are being # processed starting from the root Q = [] Q.append(root) while (len(Q) > 0) : temp = Q[0] Q.pop(0) # Take the node out of the Queue # and push it to the stack S.append(temp) # If there is a left child # then push it to the queue if (temp.left != None): Q.append(temp.left) # If there is a right child # then push it to the queue if (temp.right != None): Q.append(temp.right) # Function that returns True if the# level order traversal of the# tree results in a palindromedef isPalindrome(S,root): Q = [] Q.append(root) while (len(Q) > 0) : # To store the element at # the front of the queue temp = Q[0] # To store the element at # the top of the stack temp1 = S[-1] S.pop() Q.pop(0) # If the data in the node at the top # of stack does not match the data # in the node at the front of the queue if (temp.data != temp1.data): return False if (temp.left != None): Q.append(temp.left) if (temp.right != None): Q.append(temp.right) # If there is no mismatch return True# Driver code# Creating the binary treeroot = append('R')root.left = append('A')root.right = append('D')root.left.left = append('A')root.left.right = append('R')# Stack to store the nodes of the# tree in level order traversalS = []findInv(root, S)# If the level order traversal# results in a palindromeif (isPalindrome(S, root)): print("Yes")else: print("NO")# This code is contributed by Arnab Kundu |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{// Structure for a node of the treeclass node{ public char data; public node left, right;};// Function to.Add a node// to the Binary Treestatic node add(char data){ node newnode = new node(); newnode.data = data; newnode.left = newnode.right = null; return newnode;}// Function to perform level order traversal// of the Binary Tree and.Add the nodes to// the stackstatic void findInv(node root, Stack<node> S){ if (root == null) return; // The queue holds the nodes which are being // processed starting from the root Queue<node> Q = new Queue<node>(); Q.Enqueue(root); while (Q.Count > 0) { node temp = Q.Peek(); Q.Dequeue(); // Take the node out of the Queue // and push it to the stack S.Push(temp); // If there is a left child // then push it to the queue if (temp.left != null) Q.Enqueue(temp.left); // If there is a right child // then push it to the queue if (temp.right != null) Q.Enqueue(temp.right); }}// Function that returns true if the// level order traversal of the// tree results in a palindromestatic bool isPalindrome(Stack<node> S, node root){ Queue<node> Q = new Queue<node>(); Q.Enqueue(root); while (Q.Count > 0) { // To store the element at // the front of the queue node temp = Q.Peek(); // To store the element at // the top of the stack node temp1 = S.Peek(); S.Pop(); Q.Dequeue(); // If the data in the node at the top // of stack does not match the data // in the node at the front of the queue if (temp.data != temp1.data) return false; if (temp.left != null) Q.Enqueue(temp.left); if (temp.right != null) Q.Enqueue(temp.right); } // If there is no mismatch return true;}// Driver codepublic static void Main(String[] args){ // Creating the binary tree node root = add('R'); root.left = add('A'); root.right = add('D'); root.left.left = add('A'); root.left.right = add('R'); // Stack to store the nodes of the // tree in level order traversal Stack<node> S = new Stack<node>(); findInv(root, S); // If the level order traversal // results in a palindrome if (isPalindrome(S, root)) Console.Write("Yes"); else Console.Write("NO");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approach// Structure for a node of the treeclass node{ constructor() { this.data = ''; this.left = null; this.right = null; }};// Function to.Add a node// to the Binary Treefunction add(data){ var newnode = new node(); newnode.data = data; newnode.left = newnode.right = null; return newnode;}// Function to perform level order traversal// of the Binary Tree and.Add the nodes to// the stackfunction findInv(root, S){ if (root == null) return; // The queue holds the nodes which are being // processed starting from the root var Q = []; Q.push(root); while (Q.length > 0) { var temp = Q[0]; Q.shift(); // Take the node out of the Queue // and push it to the stack S.push(temp); // If there is a left child // then push it to the queue if (temp.left != null) Q.push(temp.left); // If there is a right child // then push it to the queue if (temp.right != null) Q.push(temp.right); }}// Function that returns true if the// level order traversal of the// tree results in a palindromefunction isPalindrome(S, root){ var Q = []; Q.push(root); while (Q.length > 0) { // To store the element at // the front of the queue var temp = Q[0]; // To store the element at // the top of the stack var temp1 = S[S.length-1]; S.pop(); Q.shift(); // If the data in the node at the top // of stack does not match the data // in the node at the front of the queue if (temp.data != temp1.data) return false; if (temp.left != null) Q.push(temp.left); if (temp.right != null) Q.push(temp.right); } // If there is no mismatch return true;}// Driver code// Creating the binary treevar root = add('R');root.left = add('A');root.right = add('D');root.left.left = add('A');root.left.right = add('R');// Stack to store the nodes of the// tree in level order traversalvar S = [];findInv(root, S);// If the level order traversal// results in a palindromeif (isPalindrome(S, root)) document.write("Yes");else document.write("NO");</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!
