Posted on by Kalkicode
Code Queue

# Print all palindromic levels of a binary tree

The given problem is to print all the palindromic levels of a binary tree. A binary tree is considered palindromic at a certain level if the values of the nodes at that level form a palindrome. A palindrome is a sequence that reads the same backward as forward.

## Problem Statement

Given a binary tree, we want to print all the levels where the values of the nodes form a palindrome.

## Explanation with Example

Consider the binary tree provided in the code:

``````
10
/   \
2     3
/     / \
4     9   4
/  \    \    \
7    3    6   11
/  \     /
2    8   2
/ \
-1   -1

``````

The levels that are palindromic in this tree are:

• Level 1: [10] (Only one node)
• Level 2: [4, 9, 4] (Palindromic)
• Level 3: [2, 8, 2] (Palindromic)
• Level 4: [-1, -1] (Palindromic)

## Idea to Solve the Problem

To solve this problem, we can perform a level-order traversal of the binary tree using a queue. For each level, we check if the nodes' values form a palindrome. If they do, we print the level. To check for a palindrome, we can use a collection (array) to store the values of the nodes at the level, and then check if the collection is the same when read in reverse.

## Code Solution

``````// C program
// Print all palindromic levels of a binary tree
#include <stdio.h>

#include <stdlib.h>

//Node of binary tree
struct Node
{
int data;
struct Node *left, *right;
};
struct MyQueue
{
int level;
struct Node *element;
struct MyQueue *next;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data)
{
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
//return reference
return new_node;
}
//Create a queue node and returns this node
struct MyQueue *enqueue(struct Node *tree_node)
{
//Make a new Queue node
struct MyQueue *new_node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (new_node != NULL)
{
//Set node values
new_node->element = tree_node;
new_node->next = NULL;
}
else
{
printf("Memory Overflow\n");
}
return new_node;
}
//Remove a queue elements
void dequeue(struct MyQueue **front)
{
if ( *front != NULL)
{
struct MyQueue *remove = *front;
//Visit to next node
*front = remove->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
int is_palindrome(struct MyQueue *front, int level)
{
if (front == NULL)
{
return 0;
}
int size = 0;
struct MyQueue *temp = front;
//Count number of nodes in given level
while (temp != NULL && temp->level == level)
{
size++;
temp = temp->next;
}
if (size == 1)
{
//When only one element in given level
return 1;
}
else
{
int collection[size];
int first = 0;
int last = size - 1;
temp = front;
//Get the nodes of given level
while (temp != NULL && temp->level == level)
{
// Get node value
collection[first] = temp->element->data;
temp = temp->next;
// Change location
first++;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection[first] != collection[last])
{
return 0;
}
first++;
last--;
}
//When palindrom exist
return 1;
}
}
//print all palindrom level nodes in binary tree
void palindrome_level(struct Node *root)
{
if (root != NULL)
{
//make a queue pointers
struct MyQueue *front = NULL, *tail = NULL;
struct MyQueue *temp = NULL;
//Get first node of tree
front = enqueue(root);
//Start level of first node is one
front->level = 1;
//Set tail node to first node
tail = front;
struct Node *node = root;
// Start to first node
temp = front;
// Get level elements into a queue
while (temp != NULL)
{
//Tree node
node = temp->element;
if (node->left != NULL)
{
tail->next = enqueue(node->left);
tail->next->level = temp->level + 1;
tail = tail->next;
}
if (node->right != NULL)
{
tail->next = enqueue(node->right);
tail->next->level = temp->level + 1;
tail = tail->next;
}
//Visit to next node queue
temp = temp->next;
}
//result node indicator
int status = 0;
int level = 0;
while (front != NULL)
{
level = front->level;
status = is_palindrome(front, level);
if (status == 1)
{
printf(" [");
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (front != NULL && front->level == level)
{
if (status == 1)
{
//When palindromic exist
printf(" %d", front->element->data);
}
//remove  a queue node
dequeue( &front);
}
if (status == 1)
{
printf(" ]\n");
}
}
tail = NULL;
}
else
{
printf("Empty Tree\n");
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
10
/   \
2     3
/     / \
4     9   4
/  \    \    \
7    3    6   11
/  \     /
2    8   2
/ \
-1   -1

-----------------------
*/
root = insert(10);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(4);
root->right->left = insert(9);
root->left->left = insert(4);
root->left->left->left = insert(7);
root->left->left->right = insert(3);
root->right->left->right = insert(6);
root->right->right->right = insert(11);
root->right->right->right->left = insert(2);
root->left->left->right->left = insert(2);
root->left->left->right->right = insert(8);
root->left->left->right->right->left = insert(-1);
root->left->left->right->right->right = insert(-1);
palindrome_level(root);
return 0;
}``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````/*
Java program
Print all palindromic levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
public boolean is_palindrome(MyQueue queue, int level)
{
if (queue.is_empty() == true)
{
return false;
}
int size = 0;
QueueNode temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size++;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return true;
}
else
{
int[] collection = new int[size];
int first = 0;
int last = size - 1;
temp = queue.front;
//Get the nodes of given level
while (temp != null && temp.level == level)
{
// Get node value
collection[first] = temp.element.data;
temp = temp.next;
// Change location
first++;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection[first] != collection[last])
{
return false;
}
first++;
last--;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
public void palindrome_level()
{
if (this.root == null)
{
System.out.print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
boolean status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = is_palindrome(queue, level);
if (status == true)
{
System.out.print(" [");
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When palindromic exist
System.out.print(" " + queue.front.element.data);
}
//remove  a queue node
queue.dequeue();
}
if (status == true)
{
System.out.print(" ]\n");
}
}
}
}
public static void main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
2     3
/     / \
4     9   4
/  \    \    \
7    3    6   11
/  \     /
2    8   2
/ \
-1   -1

-----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(2);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(-1);
tree.palindrome_level();
}
}``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````//Include header file
#include <iostream>
using namespace std;

/*
C++ program
Print all palindromic levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QueueNode
{
public:
TreeNode *element;
QueueNode *next;
int level;
QueueNode(TreeNode *element, int level)
{
this->element = element;
this->next = NULL;
this->level = level;
}
};
//Define custom queue class
class MyQueue
{
public: QueueNode *front;
QueueNode *tail;
MyQueue()
{
this->front = NULL;
this->tail = NULL;
}
//Add a new node at last of queue
void enqueue(TreeNode *element, int level)
{
QueueNode *new_node = new QueueNode(element, level);
if (this->front == NULL)
{
//When first node of queue
this->front = new_node;
}
else
{
this->tail->next = new_node;
}
this->tail = new_node;
}
//Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
//set initial tree root to null
this->root = NULL;
}
bool is_palindrome(MyQueue queue, int level)
{
if (queue.is_empty() == true)
{
return false;
}
int size = 0;
QueueNode *temp = queue.front;
//Count number of nodes in given level
while (temp != NULL && temp->level == level)
{
size++;
temp = temp->next;
}
if (size == 1)
{
//When only one element in given level
return true;
}
else
{
int collection[size];
int first = 0;
int last = size - 1;
temp = queue.front;
//Get the nodes of given level
while (temp != NULL && temp->level == level)
{
// Get node value
collection[first] = temp->element->data;
temp = temp->next;
// Change location
first++;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection[first] != collection[last])
{
return false;
}
first++;
last--;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
void palindrome_level()
{
if (this->root == NULL)
{
cout << "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
TreeNode *node = this->root;
//Create a Queue
MyQueue queue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode *temp = queue.front;
int level = 0;
while (temp != NULL)
{
node = temp->element;
level = temp->level;
if (node->left != NULL)
{
queue.enqueue(node->left, level + 1);
}
if (node->right != NULL)
{
queue.enqueue(node->right, level + 1);
}
temp = temp->next;
}
bool status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front->level;
status = this->is_palindrome(queue, level);
if (status == true)
{
cout << " [";
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front->level == level)
{
if (status == true)
{
//When palindromic exist
cout << " " << queue.front->element->data;
}
//remove  a queue node
queue.dequeue();
}
if (status == true)
{
cout << " ]\n";
}
}
}
}
};
int main()
{
//Object of Binary Tree
BinaryTree tree = BinaryTree();
tree.root = new TreeNode(10);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(3);
tree.root->right->right = new TreeNode(4);
tree.root->right->left = new TreeNode(9);
tree.root->left->left = new TreeNode(4);
tree.root->left->left->left = new TreeNode(7);
tree.root->left->left->right = new TreeNode(3);
tree.root->right->left->right = new TreeNode(6);
tree.root->right->right->right = new TreeNode(11);
tree.root->right->right->right->left = new TreeNode(2);
tree.root->left->left->right->left = new TreeNode(2);
tree.root->left->left->right->right = new TreeNode(8);
tree.root->left->left->right->right->left = new TreeNode(-1);
tree.root->left->left->right->right->right = new TreeNode(-1);
tree.palindrome_level();
return 0;
}``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````//Include namespace system
using System;

/*
C# program
Print all palindromic levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public Boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
}
public Boolean is_palindrome(MyQueue queue, int level)
{
if (queue.is_empty() == true)
{
return false;
}
int size = 0;
QueueNode temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size++;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return true;
}
else
{
int[] collection = new int[size];
int first = 0;
int last = size - 1;
temp = queue.front;
//Get the nodes of given level
while (temp != null && temp.level == level)
{
// Get node value
collection[first] = temp.element.data;
temp = temp.next;
// Change location
first++;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection[first] != collection[last])
{
return false;
}
first++;
last--;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
public void palindrome_level()
{
if (this.root == null)
{
Console.Write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
Boolean status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = is_palindrome(queue, level);
if (status == true)
{
Console.Write(" [");
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When palindromic exist
Console.Write(" " + queue.front.element.data);
}
//remove  a queue node
queue.dequeue();
}
if (status == true)
{
Console.Write(" ]\n");
}
}
}
}
public static void Main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(2);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(-1);
tree.palindrome_level();
}
}``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````<?php
/*
Php program
Print all palindromic levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
// Queue Node
class QueueNode
{
public \$element;
public \$next;
public \$level;

function __construct(\$element, \$level)
{
\$this->element = \$element;
\$this->next = null;
\$this->level = \$level;
}
}
//Define custom queue class
class MyQueue
{
public \$front;
public \$tail;

function __construct()
{
\$this->front = null;
\$this->tail = null;
}
//Add a new node at last of queue
public	function enqueue(\$element, \$level)
{
\$new_node = new QueueNode(\$element, \$level);
if (\$this->front == null)
{
//When first node of queue
\$this->front = \$new_node;
}
else
{
\$this->tail->next = \$new_node;
}
\$this->tail = \$new_node;
}
//Delete first node of queue
public	function dequeue()
{
if (\$this->front != null)
{
if (\$this->tail == \$this->front)
{
\$this->tail = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
}
}
}
public	function is_empty()
{
if (\$this->front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public \$root;

function __construct()
{
//set initial tree root to null
\$this->root = null;
}
public	function is_palindrome(\$queue, \$level)
{
if (\$queue->is_empty() == true)
{
return false;
}
\$size = 0;
\$temp = \$queue->front;
//Count number of nodes in given level
while (\$temp != null && \$temp->level == \$level)
{
\$size++;
\$temp = \$temp->next;
}
if (\$size == 1)
{
//When only one element in given level
return true;
}
else
{
\$collection = array_fill(0, \$size, 0);
\$first = 0;
\$last = \$size - 1;
\$temp = \$queue->front;
//Get the nodes of given level
while (\$temp != null && \$temp->level == \$level)
{
// Get node value
\$collection[\$first] = \$temp->element->data;
\$temp = \$temp->next;
// Change location
\$first++;
}
\$first = 0;
//Determine whether collection contains palindrome or not
while (\$first < \$last)
{
if (\$collection[\$first] != \$collection[\$last])
{
return false;
}
\$first++;
\$last--;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
public	function palindrome_level()
{
if (\$this->root == null)
{
echo "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
\$node = \$this->root;
//Create a Queue
\$queue = new MyQueue();
//Add first node at the level of one
\$queue->enqueue(\$node, 1);
\$temp = \$queue->front;
\$level = 0;
while (\$temp != null)
{
\$node = \$temp->element;
\$level = \$temp->level;
if (\$node->left != null)
{
\$queue->enqueue(\$node->left, \$level + 1);
}
if (\$node->right != null)
{
\$queue->enqueue(\$node->right, \$level + 1);
}
\$temp = \$temp->next;
}
\$status = false;
\$level = 0;
while (\$queue->is_empty() == false)
{
\$level = \$queue->front->level;
\$status = \$this->is_palindrome(\$queue, \$level);
if (\$status == true)
{
echo " [";
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (\$queue->is_empty() == false && \$queue->front->level == \$level)
{
if (\$status == true)
{
//When palindromic exist
echo " ". \$queue->front->element->data;
}
//remove  a queue node
\$queue->dequeue();
}
if (\$status == true)
{
echo " ]\n";
}
}
}
}
}

function main()
{
//Object of Binary Tree
\$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
2     3
/     / \
4     9   4
/  \    \    \
7    3    6   11
/  \     /
2    8   2
/ \
-1   -1

-----------------------
*/
\$tree->root = new TreeNode(10);
\$tree->root->left = new TreeNode(2);
\$tree->root->right = new TreeNode(3);
\$tree->root->right->right = new TreeNode(4);
\$tree->root->right->left = new TreeNode(9);
\$tree->root->left->left = new TreeNode(4);
\$tree->root->left->left->left = new TreeNode(7);
\$tree->root->left->left->right = new TreeNode(3);
\$tree->root->right->left->right = new TreeNode(6);
\$tree->root->right->right->right = new TreeNode(11);
\$tree->root->right->right->right->left = new TreeNode(2);
\$tree->root->left->left->right->left = new TreeNode(2);
\$tree->root->left->left->right->right = new TreeNode(8);
\$tree->root->left->left->right->right->left = new TreeNode(-1);
\$tree->root->left->left->right->right->right = new TreeNode(-1);
\$tree->palindrome_level();
}
main();``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````/*
Node Js program
Print all palindromic levels of a binary tree
*/
//Binary Tree node
class TreeNode
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
constructor(element, level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
enqueue(element, level)
{
var new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
constructor()
{
//set initial tree root to null
this.root = null;
}
is_palindrome(queue, level)
{
if (queue.is_empty() == true)
{
return false;
}
var size = 0;
var temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size++;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return true;
}
else
{
var collection = Array(size).fill(0);
var first = 0;
var last = size - 1;
temp = queue.front;
//Get the nodes of given level
while (temp != null && temp.level == level)
{
// Get node value
collection[first] = temp.element.data;
temp = temp.next;
// Change location
first++;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection[first] != collection[last])
{
return false;
}
first++;
last--;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
palindrome_level()
{
if (this.root == null)
{
process.stdout.write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node = this.root;
//Create a Queue
var queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp = queue.front;
var level = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
var status = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = this.is_palindrome(queue, level);
if (status == true)
{
process.stdout.write(" [");
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When palindromic exist
process.stdout.write(" " + queue.front.element.data);
}
//remove  a queue node
queue.dequeue();
}
if (status == true)
{
process.stdout.write(" ]\n");
}
}
}
}
}

function main()
{
//Object of Binary Tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
2     3
/     / \
4     9   4
/  \    \    \
7    3    6   11
/  \     /
2    8   2
/ \
-1   -1

-----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(2);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(-1);
tree.palindrome_level();
}
main();``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````#   Python 3 program
#   Print all palindromic levels of a binary tree

# Binary Tree node
class TreeNode :

def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None

#  Queue Node
class QueueNode :

def __init__(self, element, level) :
self.element = element
self.next = None
self.level = level

# Define custom queue class
class MyQueue :

def __init__(self) :
self.front = None
self.tail = None

# Add a new node at last of queue
def enqueue(self, element, level) :
new_node = QueueNode(element, level)
if (self.front == None) :
# When first node of queue
self.front = new_node
else :
# Add node at last position
self.tail.next = new_node

self.tail = new_node

# Delete first node of queue
def dequeue(self) :
if (self.front != None) :
if (self.tail == self.front) :
self.tail = None
self.front = None
else :
self.front = self.front.next

def is_empty(self) :
if (self.front == None) :
return True
else :
return False

class BinaryTree :

def __init__(self) :
# set initial tree root to null
self.root = None

def is_palindrome(self, queue, level) :
if (queue.is_empty() == True) :
return False

size = 0
temp = queue.front
# Count number of nodes in given level
while (temp != None and temp.level == level) :
size += 1
temp = temp.next

if (size == 1) :
# When only one element in given level
return True
else :
collection = [0] * (size)
first = 0
last = size - 1
temp = queue.front
# Get the nodes of given level
while (temp != None and temp.level == level) :
#  Get node value
collection[first] = temp.element.data
temp = temp.next
#  Change location
first += 1

first = 0
# Determine whether collection contains palindrome or not
while (first < last) :
if (collection[first] != collection[last]) :
return False

first += 1
last -= 1

# When palindrom exist
return True

#  Print all palindrom level nodes in binary tree
def palindrome_level(self) :
if (self.root == None) :
print("\n Empty Binary Tree \n", end = "")
else :
# Get top node in tree
node = self.root
# Create a Queue
queue = MyQueue()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
while (temp != None) :
node = temp.element
level = temp.level
if (node.left != None) :
queue.enqueue(node.left, level + 1)

if (node.right != None) :
queue.enqueue(node.right, level + 1)

temp = temp.next

status = False
level = 0
while (queue.is_empty() == False) :
level = queue.front.level
status = self.is_palindrome(queue, level)
if (status == True) :
print(" [", end = "")

#  When level nodes are palindromic,
#  Then this loop are printed node value and remove level nodes
#  Otherwise it's removing current level nodes
while (queue.is_empty() == False and queue.front.level == level) :
if (status == True) :
# When palindromic exist
print(" ", queue.front.element.data, end = "")

# remove  a queue node
queue.dequeue()

if (status == True) :
print(" ]\n", end = "")

def main() :
# Object of Binary Tree
tree = BinaryTree()
#
# 		Construct Binary Tree
# 		-----------------------
# 		           10
# 		         /   \
# 		        2     3
# 		       /     / \
# 		      4     9   4
# 		     /  \    \    \
# 		    7    3    6   11
# 		        /  \     /
# 		       2    8   2
# 		           / \
# 		         -1   -1
# 		-----------------------
#

tree.root = TreeNode(10)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.right.right = TreeNode(4)
tree.root.right.left = TreeNode(9)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(7)
tree.root.left.left.right = TreeNode(3)
tree.root.right.left.right = TreeNode(6)
tree.root.right.right.right = TreeNode(11)
tree.root.right.right.right.left = TreeNode(2)
tree.root.left.left.right.left = TreeNode(2)
tree.root.left.left.right.right = TreeNode(8)
tree.root.left.left.right.right.left = TreeNode(-1)
tree.root.left.left.right.right.right = TreeNode(-1)
tree.palindrome_level()

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

#### Output

`````` [  10 ]
[  4  9  4 ]
[  2  8  2 ]
[  -1  -1 ]``````
``````#   Ruby program
#   Print all palindromic levels of a binary tree

# 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

#  Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_accessor :element, :next, :level

def initialize(element, level)
self.element = element
self.next = nil
self.level = level
end

end

# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :front, :tail

def initialize()
self.front = nil
self.tail = nil
end

# Add a new node at last of queue
def enqueue(element, level)
new_node = QueueNode.new(element, level)
if (self.front == nil)
# When first node of queue
self.front = new_node
else
# Add node at last position
self.tail.next = new_node
end

self.tail = new_node
end

# Delete first node of queue
def dequeue()
if (self.front != nil)
if (self.tail == self.front)
self.tail = nil
self.front = nil
else
self.front = self.front.next
end

end

end

def is_empty()
if (self.front == nil)
return true
else
return false
end

end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()
# set initial tree root to null
self.root = nil
end

def is_palindrome(queue, level)
if (queue.is_empty() == true)
return false
end

size = 0
temp = queue.front
# Count number of nodes in given level
while (temp != nil && temp.level == level)
size += 1
temp = temp.next
end

if (size == 1)
# When only one element in given level
return true
else
collection = Array.new(size) {0}
first = 0
last = size - 1
temp = queue.front
# Get the nodes of given level
while (temp != nil && temp.level == level)
#  Get node value
collection[first] = temp.element.data
temp = temp.next
#  Change location
first += 1
end

first = 0
# Determine whether collection contains palindrome or not
while (first < last)
if (collection[first] != collection[last])
return false
end

first += 1
last -= 1
end

# When palindrom exist
return true
end

end

#  Print all palindrom level nodes in binary tree
def palindrome_level()
if (self.root == nil)
print("\n Empty Binary Tree \n")
else
# Get top node in tree
node = self.root
# Create a Queue
queue = MyQueue.new()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
while (temp != nil)
node = temp.element
level = temp.level
if (node.left != nil)
queue.enqueue(node.left, level + 1)
end

if (node.right != nil)
queue.enqueue(node.right, level + 1)
end

temp = temp.next
end

status = false
level = 0
while (queue.is_empty() == false)
level = queue.front.level
status = self.is_palindrome(queue, level)
if (status == true)
print(" [")
end

#  When level nodes are palindromic,
#  Then this loop are printed node value and remove level nodes
#  Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
if (status == true)
# When palindromic exist
print(" ", queue.front.element.data)
end

# remove  a queue node
queue.dequeue()
end

if (status == true)
print(" ]\n")
end

end

end

end

end

def main()
# Object of Binary Tree
tree = BinaryTree.new()
#
# 		Construct Binary Tree
# 		-----------------------
# 		           10
# 		         /   \
# 		        2     3
# 		       /     / \
# 		      4     9   4
# 		     /  \    \    \
# 		    7    3    6   11
# 		        /  \     /
# 		       2    8   2
# 		           / \
# 		         -1   -1
# 		-----------------------
#

tree.root = TreeNode.new(10)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.right.right = TreeNode.new(4)
tree.root.right.left = TreeNode.new(9)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.left = TreeNode.new(7)
tree.root.left.left.right = TreeNode.new(3)
tree.root.right.left.right = TreeNode.new(6)
tree.root.right.right.right = TreeNode.new(11)
tree.root.right.right.right.left = TreeNode.new(2)
tree.root.left.left.right.left = TreeNode.new(2)
tree.root.left.left.right.right = TreeNode.new(8)
tree.root.left.left.right.right.left = TreeNode.new(-1)
tree.root.left.left.right.right.right = TreeNode.new(-1)
tree.palindrome_level()
end

main()``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]
``````
``````/*
Scala program
Print all palindromic levels of a binary tree
*/
//Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Queue Node
class QueueNode(var element: TreeNode,
var next: QueueNode,
var level: Int)
{
def this(element: TreeNode, level: Int)
{
this(element, null, level);
}
}
//Define custom queue class
class MyQueue(var front: QueueNode,
var tail: QueueNode)
{
def this()
{
this(null, null);
}
//Add a new node at last of queue
def enqueue(element: TreeNode, level: Int): Unit = {
var new_node: QueueNode = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
def is_empty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def is_palindrome(queue: MyQueue, level: Int): Boolean = {
if (queue.is_empty() == true)
{
return false;
}
var size: Int = 0;
var temp: QueueNode = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size += 1;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return true;
}
else
{
var collection: Array[Int] = Array.fill[Int](size)(0);
var first: Int = 0;
var last: Int = size - 1;
temp = queue.front;
//Get the nodes of given level
while (temp != null && temp.level == level)
{
// Get node value
collection(first) = temp.element.data;
temp = temp.next;
// Change location
first += 1;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection(first) != collection(last))
{
return false;
}
first += 1;
last -= 1;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
def palindrome_level(): Unit = {
if (this.root == null)
{
print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node: TreeNode = this.root;
//Create a Queue
var queue: MyQueue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode = queue.front;
var level: Int = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
var status: Boolean = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front.level;
status = is_palindrome(queue, level);
if (status == true)
{
print(" [");
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it's removing current level nodes
while (queue.is_empty() == false && queue.front.level == level)
{
if (status == true)
{
//When palindromic exist
print(" " + queue.front.element.data);
}
//remove  a queue node
queue.dequeue();
}
if (status == true)
{
print(" ]\n");
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Object of Binary Tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/   \
2     3
/     / \
4     9   4
/  \    \    \
7    3    6   11
/  \     /
2    8   2
/ \
-1   -1

-----------------------
*/
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.right.right = new TreeNode(4);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.left = new TreeNode(2);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(-1);
tree.palindrome_level();
}
}``````

#### Output

`````` [ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]``````
``````/*
Swift 4 program
Print all palindromic levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode? ;
var next: QueueNode? ;
var level: Int;
init(_ element: TreeNode? , _ level : Int)
{
self.element = element;
self.next = nil;
self.level = level;
}
}
//Define custom queue class
class MyQueue
{
var front: QueueNode? ;
var tail: QueueNode? ;
init()
{
self.front = nil;
self.tail = nil;
}
//Add a new node at last of queue
func enqueue(_ element: TreeNode? , _ level : Int)
{
let new_node: QueueNode? = QueueNode(element, level);
if (self.front == nil)
{
//When first node of queue
self.front = new_node;
}
else
{
self.tail!.next = new_node;
}
self.tail = new_node;
}
//Delete first node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.tail === self.front)
{
self.tail = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
}
}
func is_empty() -> Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
//set initial tree root to null
self.root = nil;
}
func is_palindrome(_ queue: MyQueue, _ level: Int) -> Bool
{
if (queue.is_empty() == true)
{
return false;
}
var size: Int = 0;
var temp: QueueNode? = queue.front;
//Count number of nodes in given level
while (temp != nil && temp!.level == level)
{
size += 1;
temp = temp!.next;
}
if (size == 1)
{
//When only one element in given level
return true;
}
else
{
var collection: [Int] = Array(repeating: 0, count: size);
var first: Int = 0;
var last: Int = size - 1;
temp = queue.front;
//Get the nodes of given level
while (temp != nil && temp!.level == level)
{
// Get node value
collection[first] = temp!.element!.data;
temp = temp!.next;
// Change location
first += 1;
}
first = 0;
//Determine whether collection contains palindrome or not
while (first < last)
{
if (collection[first] != collection[last])
{
return false;
}
first += 1;
last -= 1;
}
//When palindrom exist
return true;
}
}
// Print all palindrom level nodes in binary tree
func palindrome_level()
{
if (self.root == nil)
{
print("\n Empty Binary Tree \n", terminator: "");
}
else
{
//Get top node in tree
var node: TreeNode? = self.root;
//Create a Queue
let queue: MyQueue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode? = queue.front;
var level: Int = 0;
while (temp != nil)
{
node = temp!.element;
level = temp!.level;
if (node!.left != nil)
{
queue.enqueue(node!.left, level + 1);
}
if (node!.right != nil)
{
queue.enqueue(node!.right, level + 1);
}
temp = temp!.next;
}
var status: Bool = false;
level = 0;
while (queue.is_empty() == false)
{
level = queue.front!.level;
status = self.is_palindrome(queue, level);
if (status == true)
{
print(" [", terminator: "");
}
// When level nodes are palindromic,
// Then this loop are printed node value and remove level nodes
// Otherwise it"s removing current level nodes
while (queue.is_empty() == false && queue.front!.level == level)
{
if (status == true)
{
//When palindromic exist
print(" ", queue.front!.element!.data, terminator: "");
}
//remove  a queue node
queue.dequeue();
}
if (status == true)
{
print(" ]\n", terminator: "");
}
}
}
}
}
func main()
{
//Object of Binary Tree
let tree: BinaryTree = BinaryTree();
tree.root = TreeNode(10);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.right!.right = TreeNode(4);
tree.root!.right!.left = TreeNode(9);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.left = TreeNode(7);
tree.root!.left!.left!.right = TreeNode(3);
tree.root!.right!.left!.right = TreeNode(6);
tree.root!.right!.right!.right = TreeNode(11);
tree.root!.right!.right!.right!.left = TreeNode(2);
tree.root!.left!.left!.right!.left = TreeNode(2);
tree.root!.left!.left!.right!.right = TreeNode(8);
tree.root!.left!.left!.right!.right!.left = TreeNode(-1);
tree.root!.left!.left!.right!.right!.right = TreeNode(-1);
tree.palindrome_level();
}
main();``````

#### Output

`````` [  10 ]
[  4  9  4 ]
[  2  8  2 ]
[  -1  -1 ]``````

## Algorithm Explanation

1. Define the `TreeNode` class to represent a node in the binary tree. Each node has a value, a left child, and a right child.
2. Define the `QueueNode` class to represent a node in the queue. Each node has a reference to a tree node, a reference to the next node, and the level of the tree node it points to.
3. Define the `MyQueue` class to implement a custom queue that supports enqueue, dequeue, and is_empty operations.
4. Create a `BinaryTree` class to represent the binary tree. It has a `root` variable that holds the reference to the root node of the tree.
5. Implement the `is_palindrome` function that checks if the nodes' values at a given level form a palindrome.
6. Implement the `palindrome_level` function to print all the palindromic levels of the binary tree. It uses a queue to perform the level-order traversal and checks each level for palindromes using the `is_palindrome` function.
7. Create a binary tree with the given nodes and call the `palindrome_level` function to print the palindromic levels.

## Resultant Output Explanation

The program executes the `palindrome_level` function and prints the levels that are palindromic for the given binary tree. The output is:

``````[ 10 ]
[ 4 9 4 ]
[ 2 8 2 ]
[ -1 -1 ]
``````

These are the levels whose nodes' values form palindromes in the given binary tree.

## Time Complexity

The time complexity of the code is O(n^2), where 'n' is the number of nodes in the binary tree. This is because for each level, we count the number of nodes in that level, which takes O(n) time. Additionally, to check if the values in that level form a palindrome, we use an array to store the values, and checking for a palindrome takes O(n) time in the worst case. Therefore, for each level, we perform O(n) operations, and we have a total of 'n' levels in the binary tree, resulting in an overall time complexity of O(n^2).

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