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
		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

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.

New Comment





Categories
Relative Post