Check if inorder of binary tree is form of palindrome or not
Here given code implementation process.
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
record.add(node.data);
// 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
record.Add(node.data);
// 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_reader :data, :left, :right
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_reader :root
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
record.add(node.data);
// 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
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.
New Comment