Given a binary tree and the task if to check if its Inorder Sequence is a palindrome or not.
Examples:
Input:
Output: True
Explanation:
The Inorder sequence of the tree is “bbaaabb” which is a palindromic string.
Input:
Output: False
Explanation:
The Inorder sequence of the tree is “bbdaabb” which is not a palindromic string.
Approach:
To solve the problem, refer to the following steps:
- Convert the given Binary Tree to a Doubly Linked List.
- This, reduces the problem to Check if a doubly linked list of characters is palindrome or not.
Below is the implementation of above approach:
C++
// C++ Program to check if// the Inorder sequence of a// Binary Tree is a palindrome#include <bits/stdc++.h>using namespace std;// Define node of treestruct node { char val; node* left; node* right;};// Function to create the nodenode* newnode(char i){ node* temp = NULL; temp = new node(); temp->val = i; temp->left = NULL; temp->right = NULL; return temp;}// Function to convert the tree// to the double linked listnode* conv_tree(node* root, node* shoot){ if (root->left != NULL) shoot = conv_tree(root->left, shoot); root->left = shoot; if (shoot != NULL) shoot->right = root; shoot = root; if (root->right != NULL) shoot = conv_tree(root->right, shoot); return shoot;}// Function for checking linked// list is palindrome or notint checkPalin(node* root){ node* voot = root; // Count the nodes // form the back int j = 0; // Set the pointer at the // very first node of the // linklist and count the // length of the linklist while (voot->left != NULL) { j = j + 1; voot = voot->left; } int i = 0; while (i < j) { // Check if the value matches if (voot->val != root->val) return 0; else { i = i + 1; j = j - 1; voot = voot->right; root = root->left; } } return 1;}// Driver Programint main(){ node* root = newnode('b'); root->left = newnode('b'); root->right = newnode('a'); root->left->right = newnode('b'); root->left->left = newnode('a'); node* shoot = conv_tree(root, NULL); if (checkPalin(shoot)) cout << "True" << endl; else cout << "False" << endl;} |
Java
// Java Program to check if// the Inorder sequence of a// Binary Tree is a palindromeimport java.util.*;class GFG{// Define node of treestatic class node{ char val; node left; node right;};// Function to create the nodestatic node newnode(char i){ node temp = null; temp = new node(); temp.val = i; temp.left = null; temp.right = null; return temp;}// Function to convert the tree// to the double linked liststatic node conv_tree(node root, node shoot){ if (root.left != null) shoot = conv_tree(root.left, shoot); root.left = shoot; if (shoot != null) shoot.right = root; shoot = root; if (root.right != null) shoot = conv_tree(root.right, shoot); return shoot;}// Function for checking linked// list is palindrome or notstatic int checkPalin(node root){ node voot = root; // Count the nodes // form the back int j = 0; // Set the pointer at the // very first node of the // linklist and count the // length of the linklist while (voot.left != null) { j = j + 1; voot = voot.left; } int i = 0; while (i < j) { // Check if the value matches if (voot.val != root.val) return 0; else { i = i + 1; j = j - 1; voot = voot.right; root = root.left; } } return 1;}// Driver Codepublic static void main(String[] args){ node root = newnode('b'); root.left = newnode('b'); root.right = newnode('a'); root.left.right = newnode('b'); root.left.left = newnode('a'); node shoot = conv_tree(root, null); if (checkPalin(shoot) == 1) System.out.print("True" + "\n"); else System.out.print("False" + "\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to check if# the Inorder sequence of a# Binary Tree is a palindrome# Define node of treeclass Node: def __init__(self,val): self.val = val self.left = None self.right = None# Function to create the nodedef newnode(i): #temp = None; temp = Node(i); temp.val = i; temp.left = None; temp.right = None; return temp;# Function to convert the tree# to the double linked listdef conv_tree(root, shoot): if (root.left != None): shoot = conv_tree(root.left, shoot); root.left = shoot; if (shoot != None): shoot.right = root; shoot = root; if (root.right != None): shoot = conv_tree(root.right, shoot); return shoot;# Function for checking linked# list is palindrome or notdef checkPalin(root): voot = root; # Count the nodes # form the back j = 0; # Set the pointer at the # very first node of the # linklist and count the # length of the linklist while (voot.left != None): j = j + 1; voot = voot.left; i = 0; while (i < j): # Check if the value matches if (voot.val != root.val): return 0; else: i = i + 1; j = j - 1; voot = voot.right; root = root.left; return 1;# Driver codeif __name__=='__main__': root = newnode('b'); root.left = newnode('b'); root.right = newnode('a'); root.left.right = newnode('b'); root.left.left = newnode('a'); shoot = conv_tree(root, None); if (checkPalin(shoot)): print("True"); else: print("False");# This code is contributed by AbhiThakur |
C#
// C# program to check if the inorder // sequence of a Binary Tree is a // palindromeusing System;class GFG{// Define node of treeclass node{ public char val; public node left; public node right;};// Function to create the nodestatic node newnode(char i){ node temp = null; temp = new node(); temp.val = i; temp.left = null; temp.right = null; return temp;}// Function to convert the tree// to the double linked liststatic node conv_tree(node root, node shoot){ if (root.left != null) shoot = conv_tree(root.left, shoot); root.left = shoot; if (shoot != null) shoot.right = root; shoot = root; if (root.right != null) shoot = conv_tree(root.right, shoot); return shoot;}// Function for checking linked// list is palindrome or notstatic int checkPalin(node root){ node voot = root; // Count the nodes // form the back int j = 0; // Set the pointer at the // very first node of the // linklist and count the // length of the linklist while (voot.left != null) { j = j + 1; voot = voot.left; } int i = 0; while (i < j) { // Check if the value matches if (voot.val != root.val) return 0; else { i = i + 1; j = j - 1; voot = voot.right; root = root.left; } } return 1;}// Driver Codepublic static void Main(String[] args){ node root = newnode('b'); root.left = newnode('b'); root.right = newnode('a'); root.left.right = newnode('b'); root.left.left = newnode('a'); node shoot = conv_tree(root, null); if (checkPalin(shoot) == 1) Console.Write("True" + "\n"); else Console.Write("False" + "\n");}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to check if the inorder // sequence of a Binary Tree is a // palindrome // Define node of tree class node { constructor() { this.val = 0; this.left = null; this.right = null; } } // Function to create the node function newnode(i) { var temp = null; temp = new node(); temp.val = i; temp.left = null; temp.right = null; return temp; } // Function to convert the tree // to the double linked list function conv_tree(root, shoot) { if (root.left != null) shoot = conv_tree(root.left, shoot); root.left = shoot; if (shoot != null) shoot.right = root; shoot = root; if (root.right != null) shoot = conv_tree(root.right, shoot); return shoot; } // Function for checking linked // list is palindrome or not function checkPalin(root) { var voot = root; // Count the nodes // form the back var j = 0; // Set the pointer at the // very first node of the // linklist and count the // length of the linklist while (voot.left != null) { j = j + 1; voot = voot.left; } var i = 0; while (i < j) { // Check if the value matches if (voot.val != root.val) return 0; else { i = i + 1; j = j - 1; voot = voot.right; root = root.left; } } return 1; } // Driver Code var root = newnode("b"); root.left = newnode("b"); root.right = newnode("a"); root.left.right = newnode("b"); root.left.left = newnode("a"); var shoot = conv_tree(root, null); if (checkPalin(shoot) == 1) document.write("True" + "<br>"); else document.write("False" + "<br>"); // This code is contributed by rdtank. </script> |
Output:
True
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
