Posted on by Kalkicode
Code Recursion

# Check if inorder of binary tree is form of palindrome or not

The problem is to determine whether the in-order traversal of a given binary tree forms a palindrome or not.

## Problem Statement

Given a binary tree, the task is to check if the in-order traversal of the tree forms a palindrome or not.

## Example Scenario

Consider the binary tree shown below:

``````
a
/ \
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b``````

For this tree, the in-order traversal sequence is `[b, c, d, e, a, a, e, d, c, b]`, which is a palindrome.

## Idea to Solve the Problem

To determine whether the in-order traversal sequence is a palindrome, we can compare the characters from both ends of the sequence. We start by comparing the first and last characters, then the second and second-to-last characters, and so on.

## Pseudocode

``````boolean isPalindrome(ArrayList record)
{
int i = 0;
while (i <= record.size() / 2)
{
if (record.get(i) != record.get(record.size() - 1 - i))
return false;
i++;
}
return true;
}``````

## Algorithm Explanation

1. Implement a function `isPalindrome` that takes an `ArrayList` of characters as input.
2. Initialize an index `i` to 0 and iterate through the `ArrayList` up to the middle.
3. Compare the character at index `i` with the character at index `size - 1 - i`. If they are not equal, return `false`.
4. If the loop completes without finding any mismatch, return `true`, indicating that the sequence is a palindrome.

## Code Solution

``````import java.util.ArrayList;
/*
Java program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
class TreeNode
{
public char data;
public TreeNode left;
public TreeNode right;
public TreeNode(char data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
public boolean isPalindrome(ArrayList < Character > record)
{
int i = 0;
// Detect non palindromic pair
while (i <= record.size() / 2)
{
// Check pairwise first and last element
if (record.get(i) != record.get(record.size() - 1 - i))
{
// When pair are not same
return false;
}
i++;
}
return true;
}
public void getInorder(TreeNode node,
ArrayList < Character > record)
{
if (node == null)
{
return;
}
// Visit left subtree
getInorder(node.left, record);
// Add node value into record
// Visit right subtree
getInorder(node.right, record);
}
// This is display the inorder sequence
// of given root of binary tree
public void printInorder(TreeNode node)
{
if (node == null)
{
return;
}
// Visit left subtree
printInorder(node.left);
// Display node value
System.out.print("  " + node.data);
// Visit right subtree
printInorder(node.right);
}
public void isInorderPalindrome()
{
boolean result = true;
if (this.root == null)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
ArrayList < Character > record = new ArrayList < Character > ();
getInorder(this.root, record);
// Check inorder is palindrome
result = isPalindrome(record);
}
// Display inorder of binary tree
printInorder(this.root);
if (result == true)
{
System.out.print("\n  Yes \n");
}
else
{
System.out.print("\n  No \n");
}
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('e');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('a');
tree1.root.left.left = new TreeNode('b');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('c');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('d');
// Test A
tree1.isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('e');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('b');
tree2.root.right = new TreeNode('a');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('d');
tree2.root.right.right.left = new TreeNode('b');
// Test B
tree2.isInorderPalindrome();
}
}``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````
``````// Include header file
#include <iostream>
#include <vector>
using namespace std;

/*
C++ program
Check if inorder of binary tree is form of palindrome or not
*/

// Binary Tree node
class TreeNode
{
public:
char data;
TreeNode *left;
TreeNode *right;
TreeNode(char data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
bool isPalindrome(vector < char > record)
{
int i = 0;
// Detect non palindromic pair
while (i <= record.size() / 2)
{
// Check pairwise first and last element
if (record.at(i) != record.at(record.size() - 1 - i))
{
// When pair are not same
return false;
}
i++;
}
return true;
}
void getInorder(TreeNode *node, vector < char > &record)
{
if (node == NULL)
{
return;
}
// Visit left subtree
this->getInorder(node->left, record);
// Add node value into record
record.push_back(node->data);
// Visit right subtree
this->getInorder(node->right, record);
}
// This is display the inorder sequence
// of given root of binary tree
void printInorder(TreeNode *node)
{
if (node == NULL)
{
return;
}
// Visit left subtree
this->printInorder(node->left);
// Display node value
cout << "  " << node->data;
// Visit right subtree
this->printInorder(node->right);
}
void isInorderPalindrome()
{
bool result = true;
if (this->root == NULL)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
vector < char > record ;
this->getInorder(this->root, record);
// Check inorder is palindrome
result = this->isPalindrome(record);
}
// Display inorder of binary tree
this->printInorder(this->root);
if (result == true)
{
cout << "\n  Yes \n";
}
else
{
cout << "\n  No \n";
}
}
};
int main()
{
// Create new binary tree
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1->root = new TreeNode('a');
tree1->root->left = new TreeNode('c');
tree1->root->left->right = new TreeNode('e');
tree1->root->left->right->left = new TreeNode('d');
tree1->root->left->right->right = new TreeNode('a');
tree1->root->left->left = new TreeNode('b');
tree1->root->right = new TreeNode('e');
tree1->root->right->right = new TreeNode('c');
tree1->root->right->right->right = new TreeNode('b');
tree1->root->right->right->left = new TreeNode('d');
// Test A
tree1->isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2->root = new TreeNode('a');
tree2->root->left = new TreeNode('a');
tree2->root->left->right = new TreeNode('e');
tree2->root->left->right->left = new TreeNode('d');
tree2->root->left->right->right = new TreeNode('b');
tree2->root->right = new TreeNode('a');
tree2->root->right->right = new TreeNode('e');
tree2->root->right->right->right = new TreeNode('d');
tree2->root->right->right->left = new TreeNode('b');
// Test B
tree2->isInorderPalindrome();
return 0;
}``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
public class TreeNode
{
public char data;
public TreeNode left;
public TreeNode right;
public TreeNode(char data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
public Boolean isPalindrome(List < char > record)
{
int i = 0;
// Detect non palindromic pair
while (i <= record.Count / 2)
{
// Check pairwise first and last element
if (record[i] != record[record.Count - 1 - i])
{
// When pair are not same
return false;
}
i++;
}
return true;
}
public void getInorder(TreeNode node, List < char > record)
{
if (node == null)
{
return;
}
// Visit left subtree
this.getInorder(node.left, record);
// Add node value into record
// Visit right subtree
this.getInorder(node.right, record);
}
// This is display the inorder sequence
// of given root of binary tree
public void printInorder(TreeNode node)
{
if (node == null)
{
return;
}
// Visit left subtree
this.printInorder(node.left);
// Display node value
Console.Write("  " + node.data);
// Visit right subtree
this.printInorder(node.right);
}
public void isInorderPalindrome()
{
Boolean result = true;
if (this.root == null)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
List < char > record = new List < char > ();
this.getInorder(this.root, record);
// Check inorder is palindrome
result = this.isPalindrome(record);
}
// Display inorder of binary tree
this.printInorder(this.root);
if (result == true)
{
Console.Write("\n  Yes \n");
}
else
{
Console.Write("\n  No \n");
}
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('e');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('a');
tree1.root.left.left = new TreeNode('b');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('c');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('d');
// Test A
tree1.isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('e');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('b');
tree2.root.right = new TreeNode('a');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('d');
tree2.root.right.right.left = new TreeNode('b');
// Test B
tree2.isInorderPalindrome();
}
}``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````
``````<?php
/*
Php program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
public	function isPalindrome(\$record)
{
\$i = 0;
// Detect non palindromic pair
while (\$i <= (int)(count(\$record) / 2))
{
// Check pairwise first and last element
if (\$record[\$i] != \$record[count(\$record) - 1 - \$i])
{
// When pair are not same
return false;
}
\$i++;
}
return true;
}
public	function getInorder(\$node, &\$record)
{
if (\$node == NULL)
{
return;
}
// Visit left subtree
\$this->getInorder(\$node->left, \$record);
// Add node value into record
\$record[] = \$node->data;
// Visit right subtree
\$this->getInorder(\$node->right, \$record);
}
// This is display the inorder sequence
// of given root of binary tree
public	function printInorder(\$node)
{
if (\$node == NULL)
{
return;
}
// Visit left subtree
\$this->printInorder(\$node->left);
// Display node value
echo("  ".\$node->data);
// Visit right subtree
\$this->printInorder(\$node->right);
}
public	function isInorderPalindrome()
{
\$result = true;
if (\$this->root == NULL)
{
// Empty Tree
\$result = false;
}
else
{
// This is used to collect inorder sequence
\$record = array();
\$this->getInorder(\$this->root, \$record);
// Check inorder is palindrome
\$result = \$this->isPalindrome(\$record);
}
// Display inorder of binary tree
\$this->printInorder(\$this->root);
if (\$result == true)
{
echo("\n  Yes \n");
}
else
{
echo("\n  No \n");
}
}
}

function main()
{
// Create new binary tree
\$tree1 = new BinaryTree();
\$tree2 = new BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
\$tree1->root = new TreeNode('a');
\$tree1->root->left = new TreeNode('c');
\$tree1->root->left->right = new TreeNode('e');
\$tree1->root->left->right->left = new TreeNode('d');
\$tree1->root->left->right->right = new TreeNode('a');
\$tree1->root->left->left = new TreeNode('b');
\$tree1->root->right = new TreeNode('e');
\$tree1->root->right->right = new TreeNode('c');
\$tree1->root->right->right->right = new TreeNode('b');
\$tree1->root->right->right->left = new TreeNode('d');
// Test A
\$tree1->isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
\$tree2->root = new TreeNode('a');
\$tree2->root->left = new TreeNode('a');
\$tree2->root->left->right = new TreeNode('e');
\$tree2->root->left->right->left = new TreeNode('d');
\$tree2->root->left->right->right = new TreeNode('b');
\$tree2->root->right = new TreeNode('a');
\$tree2->root->right->right = new TreeNode('e');
\$tree2->root->right->right->right = new TreeNode('d');
\$tree2->root->right->right->left = new TreeNode('b');
// Test B
\$tree2->isInorderPalindrome();
}
main();``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````
``````/*
Node JS program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
isPalindrome(record)
{
var i = 0;
// Detect non palindromic pair
while (i <= parseInt(record.length / 2))
{
// Check pairwise first and last element
if (record[i] != record[record.length - 1 - i])
{
// When pair are not same
return false;
}
i++;
}
return true;
}
getInorder(node, record)
{
if (node == null)
{
return;
}
// Visit left subtree
this.getInorder(node.left, record);
// Add node value into record
record.push(node.data);
// Visit right subtree
this.getInorder(node.right, record);
}
// This is display the inorder sequence
// of given root of binary tree
printInorder(node)
{
if (node == null)
{
return;
}
// Visit left subtree
this.printInorder(node.left);
// Display node value
process.stdout.write("  " + node.data);
// Visit right subtree
this.printInorder(node.right);
}
isInorderPalindrome()
{
var result = true;
if (this.root == null)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
var record = [];
this.getInorder(this.root, record);
// Check inorder is palindrome
result = this.isPalindrome(record);
}
// Display inorder of binary tree
this.printInorder(this.root);
if (result == true)
{
process.stdout.write("\n  Yes \n");
}
else
{
process.stdout.write("\n  No \n");
}
}
}

function main()
{
// Create new binary tree
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('e');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('a');
tree1.root.left.left = new TreeNode('b');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('c');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('d');
// Test A
tree1.isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('e');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('b');
tree2.root.right = new TreeNode('a');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('d');
tree2.root.right.right.left = new TreeNode('b');
// Test B
tree2.isInorderPalindrome();
}
main();``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````
``````#  Python 3 program
#  Check if inorder of binary tree is form of palindrome or not

#  Binary Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

class BinaryTree :
def __init__(self) :
self.root = None

def isPalindrome(self, record) :
i = 0
#  Detect non palindromic pair
while (i <= int(len(record) / 2)) :
#  Check pairwise first and last element
if (record[i] != record[len(record) - 1 - i]) :
#  When pair are not same
return False

i += 1

return True

def getInorder(self, node, record) :
if (node == None) :
return

#  Visit left subtree
self.getInorder(node.left, record)
#  Add node value into record
record.append(node.data)
#  Visit right subtree
self.getInorder(node.right, record)

#  This is display the inorder sequence
#  of given root of binary tree
def printInorder(self, node) :
if (node == None) :
return

#  Visit left subtree
self.printInorder(node.left)
#  Display node value
print("  ", node.data, end = "")
#  Visit right subtree
self.printInorder(node.right)

def isInorderPalindrome(self) :
result = True
if (self.root == None) :
#  Empty Tree
result = False
else :
#  This is used to collect inorder sequence
record = []
self.getInorder(self.root, record)
#  Check inorder is palindrome
result = self.isPalindrome(record)

#  Display inorder of binary tree
self.printInorder(self.root)
if (result == True) :
print("\n  Yes ")
else :
print("\n  No ")

def main() :
#  Create new binary tree
tree1 = BinaryTree()
tree2 = BinaryTree()
#         a
#       /   \
#      c     e
#     / \     \
#    b   e     c
#       / \   / \
#      d   a d   b
# -----------------
# Constructing binary tree
tree1.root = TreeNode('a')
tree1.root.left = TreeNode('c')
tree1.root.left.right = TreeNode('e')
tree1.root.left.right.left = TreeNode('d')
tree1.root.left.right.right = TreeNode('a')
tree1.root.left.left = TreeNode('b')
tree1.root.right = TreeNode('e')
tree1.root.right.right = TreeNode('c')
tree1.root.right.right.right = TreeNode('b')
tree1.root.right.right.left = TreeNode('d')
#  Test A
tree1.isInorderPalindrome()
#         a
#       /   \
#      a     a
#       \     \
#        e     e
#       / \   / \
#      d   b b   d
# -----------------
# Constructing binary tree
tree2.root = TreeNode('a')
tree2.root.left = TreeNode('a')
tree2.root.left.right = TreeNode('e')
tree2.root.left.right.left = TreeNode('d')
tree2.root.left.right.right = TreeNode('b')
tree2.root.right = TreeNode('a')
tree2.root.right.right = TreeNode('e')
tree2.root.right.right.right = TreeNode('d')
tree2.root.right.right.left = TreeNode('b')
#  Test B
tree2.isInorderPalindrome()

if __name__ == "__main__": main()``````

#### input

``````   b   c   d   e   a   a   e   d   c   b
Yes
a   d   e   b   a   a   b   e   d
No``````
``````#  Ruby program
#  Check if inorder of binary tree is form of palindrome or not

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root
def initialize()
self.root = nil
end

def isPalindrome(record)
i = 0
#  Detect non palindromic pair
while (i <= record.length / 2)
#  Check pairwise first and last element
if (record[i] != record[record.length - 1 - i])
#  When pair are not same
return false
end

i += 1
end

return true
end

def getInorder(node, record)
if (node == nil)
return
end

#  Visit left subtree
self.getInorder(node.left, record)
#  Add node value into record
record.push(node.data)
#  Visit right subtree
self.getInorder(node.right, record)
end

#  This is display the inorder sequence
#  of given root of binary tree
def printInorder(node)
if (node == nil)
return
end

#  Visit left subtree
self.printInorder(node.left)
#  Display node value
print("  ", node.data)
#  Visit right subtree
self.printInorder(node.right)
end

def isInorderPalindrome()
result = true
if (self.root == nil)
#  Empty Tree
result = false
else
#  This is used to collect inorder sequence
record = []
self.getInorder(self.root, record)
#  Check inorder is palindrome
result = self.isPalindrome(record)
end

#  Display inorder of binary tree
self.printInorder(self.root)
if (result == true)
print("\n  Yes \n")
else

print("\n  No \n")
end

end

end

def main()
#  Create new binary tree
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
#         a
#       /   \
#      c     e
#     / \     \
#    b   e     c
#       / \   / \
#      d   a d   b
# -----------------
# Constructing binary tree
tree1.root = TreeNode.new('a')
tree1.root.left = TreeNode.new('c')
tree1.root.left.right = TreeNode.new('e')
tree1.root.left.right.left = TreeNode.new('d')
tree1.root.left.right.right = TreeNode.new('a')
tree1.root.left.left = TreeNode.new('b')
tree1.root.right = TreeNode.new('e')
tree1.root.right.right = TreeNode.new('c')
tree1.root.right.right.right = TreeNode.new('b')
tree1.root.right.right.left = TreeNode.new('d')
#  Test A
tree1.isInorderPalindrome()
#         a
#       /   \
#      a     a
#       \     \
#        e     e
#       / \   / \
#      d   b b   d
# -----------------
# Constructing binary tree
tree2.root = TreeNode.new('a')
tree2.root.left = TreeNode.new('a')
tree2.root.left.right = TreeNode.new('e')
tree2.root.left.right.left = TreeNode.new('d')
tree2.root.left.right.right = TreeNode.new('b')
tree2.root.right = TreeNode.new('a')
tree2.root.right.right = TreeNode.new('e')
tree2.root.right.right.right = TreeNode.new('d')
tree2.root.right.right.left = TreeNode.new('b')
#  Test B
tree2.isInorderPalindrome()
end

main()``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No
``````
``````import scala.collection.mutable._;
/*
Scala program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
class TreeNode(var data: Char,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Char)
{
// Set node value
this(data, null,null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def isPalindrome(record: ArrayBuffer[Character]): Boolean = {
var i: Int = 0;
// Detect non palindromic pair
while (i <= record.size / 2)
{
// Check pairwise first and last element
if (record(i) != record(record.size - 1 - i))
{
// When pair are not same
return false;
}
i += 1;
}
return true;
}
def getInorder(node: TreeNode, record: ArrayBuffer[Character]): Unit = {
if (node == null)
{
return;
}
// Visit left subtree
getInorder(node.left, record);
// Add node value into record
record += node.data;
// Visit right subtree
getInorder(node.right, record);
}
// This is display the inorder sequence
// of given root of binary tree
def printInorder(node: TreeNode): Unit = {
if (node == null)
{
return;
}
// Visit left subtree
printInorder(node.left);
// Display node value
print("  " + node.data);
// Visit right subtree
printInorder(node.right);
}
def isInorderPalindrome(): Unit = {
var result: Boolean = true;
if (this.root == null)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
var record: ArrayBuffer[Character] = new ArrayBuffer[Character]();
getInorder(this.root, record);
// Check inorder is palindrome
result = isPalindrome(record);
}
// Display inorder of binary tree
printInorder(this.root);
if (result == true)
{
print("\n  Yes \n");
}
else
{
print("\n  No \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create new binary tree
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('e');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('a');
tree1.root.left.left = new TreeNode('b');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('c');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('d');
// Test A
tree1.isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('e');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('b');
tree2.root.right = new TreeNode('a');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('d');
tree2.root.right.right.left = new TreeNode('b');
// Test B
tree2.isInorderPalindrome();
}
}``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````
``````import Foundation;
/*
Swift 4 program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
class TreeNode
{
var data: Character;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Character)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func isPalindrome(_ record: [Character]) -> Bool
{
var i = 0;
// Detect non palindromic pair
while (i <= record.count / 2)
{
// Check pairwise first and last element
if (!(record[i] == record[record.count - 1 - i]))
{
// When pair are not same
return false;
}
i += 1;
}
return true;
}
func getInorder(_ node: TreeNode? , _ record : inout[Character])
{
if (node == nil)
{
return;
}
// Visit left subtree
self.getInorder(node!.left, &record);
// Add node value into record
record.append(node!.data);
// Visit right subtree
self.getInorder(node!.right, &record);
}
// This is display the inorder sequence
// of given root of binary tree
func printInorder(_ node: TreeNode? )
{
if (node == nil)
{
return;
}
// Visit left subtree
self.printInorder(node?.left);
// Display node value
print("  ", node!.data, terminator: "");
// Visit right subtree
self.printInorder(node?.right);
}
func isInorderPalindrome()
{
var result = true;
if (self.root == nil)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
var record = [Character]();
self.getInorder(self.root, &record);
// Check inorder is palindrome
result = self.isPalindrome(record);
}
// Display inorder of binary tree
self.printInorder(self.root);
if (result == true)
{
print("\n  Yes ");
}
else
{
print("\n  No ");
}
}
}
func main()
{
// Create new binary tree
let tree1 = BinaryTree();
let tree2 = BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1.root = TreeNode("a");
tree1.root!.left = TreeNode("c");
tree1.root!.left!.right = TreeNode("e");
tree1.root!.left!.right!.left = TreeNode("d");
tree1.root!.left!.right!.right = TreeNode("a");
tree1.root!.left!.left = TreeNode("b");
tree1.root!.right = TreeNode("e");
tree1.root!.right!.right = TreeNode("c");
tree1.root!.right!.right!.right = TreeNode("b");
tree1.root!.right!.right!.left = TreeNode("d");
// Test A
tree1.isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2.root = TreeNode("a");
tree2.root!.left = TreeNode("a");
tree2.root!.left!.right = TreeNode("e");
tree2.root!.left!.right!.left = TreeNode("d");
tree2.root!.left!.right!.right = TreeNode("b");
tree2.root!.right = TreeNode("a");
tree2.root!.right!.right = TreeNode("e");
tree2.root!.right!.right!.right = TreeNode("d");
tree2.root!.right!.right!.left = TreeNode("b");
// Test B
tree2.isInorderPalindrome();
}
main();``````

#### input

``````   b   c   d   e   a   a   e   d   c   b
Yes
a   d   e   b   a   a   b   e   d
No``````
``````/*
Kotlin program
Check if inorder of binary tree is form of palindrome or not
*/
// Binary Tree node
class TreeNode
{
var data: Char;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Char)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun isPalindrome(record: MutableList < Char >  ): Boolean
{
var i: Int = 0;
// Detect non palindromic pair
while (i <= record.size / 2)
{
// Check pairwise first and last element
if (record[i] != record[record.size - 1 - i])
{
// When pair are not same
return false;
}
i += 1;
}
return true;
}
fun getInorder(node: TreeNode ? , record : MutableList < Char >  ): Unit
{
if (node == null)
{
return;
}
// Visit left subtree
this.getInorder(node.left, record);
// Add node value into record
// Visit right subtree
this.getInorder(node.right, record);
}
// This is display the inorder sequence
// of given root of binary tree
fun printInorder(node: TreeNode ? ): Unit
{
if (node == null)
{
return;
}
// Visit left subtree
this.printInorder(node.left);
// Display node value
print("  " + node.data);
// Visit right subtree
this.printInorder(node.right);
}
fun isInorderPalindrome(): Unit
{
var result: Boolean ;
if (this.root == null)
{
// Empty Tree
result = false;
}
else
{
// This is used to collect inorder sequence
val record = mutableListOf < Char > ();
this.getInorder(this.root, record);
// Check inorder is palindrome
result = this.isPalindrome(record);
}
// Display inorder of binary tree
this.printInorder(this.root);
if (result == true)
{
print("\n  Yes \n");
}
else
{
print("\n  No \n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
/*
a
/   \
c     e
/ \     \
b   e     c
/ \   / \
d   a d   b
-----------------
Constructing binary tree
*/
tree1.root = TreeNode('a');
tree1.root?.left = TreeNode('c');
tree1.root?.left?.right = TreeNode('e');
tree1.root?.left?.right?.left = TreeNode('d');
tree1.root?.left?.right?.right = TreeNode('a');
tree1.root?.left?.left = TreeNode('b');
tree1.root?.right = TreeNode('e');
tree1.root?.right?.right = TreeNode('c');
tree1.root?.right?.right?.right = TreeNode('b');
tree1.root?.right?.right?.left = TreeNode('d');
// Test A
tree1.isInorderPalindrome();
/*
a
/   \
a     a
\     \
e     e
/ \   / \
d   b b   d
-----------------
Constructing binary tree
*/
tree2.root = TreeNode('a');
tree2.root?.left = TreeNode('a');
tree2.root?.left?.right = TreeNode('e');
tree2.root?.left?.right?.left = TreeNode('d');
tree2.root?.left?.right?.right = TreeNode('b');
tree2.root?.right = TreeNode('a');
tree2.root?.right?.right = TreeNode('e');
tree2.root?.right?.right?.right = TreeNode('d');
tree2.root?.right?.right?.left = TreeNode('b');
// Test B
tree2.isInorderPalindrome();
}``````

#### input

``````  b  c  d  e  a  a  e  d  c  b
Yes
a  d  e  b  a  a  b  e  d
No``````

## Output Explanation

The code implements the algorithm and checks whether the in-order traversal sequence of the binary tree forms a palindrome or not. It displays the in-order traversal sequence and outputs "Yes" if it's a palindrome and "No" otherwise.

## Time Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we perform a single iteration through the in-order traversal sequence to check for palindrome property. The space complexity is O(N) due to the space required to store the in-order traversal sequence.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post