Posted on by Kalkicode
Code Recursion

# Count tree paths whose permutation is palindrome

The problem involves counting the number of paths in a binary tree for which the permutation of the nodes along the path forms a palindrome.

## Problem Statement

Given a binary tree, the task is to count the number of paths such that the permutation of the nodes along the path results in a palindrome.

## Example Scenario

Consider the binary tree shown below:

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

For this tree, the paths `[a, c, a]`, `[a, c, c, a]`, `[a, e, e, a]` are examples of paths where the permutation of nodes forms a palindrome.

## Idea to Solve the Problem

To solve this problem, we can use a recursive approach to traverse the binary tree and keep track of the frequency of characters along the path. We will create a `HashMap` to store the character frequencies. For each leaf node, we check if the frequencies of characters in the path would allow the permutation to be a palindrome.

## Pseudocode

``````boolean isPalindrome(HashMap record)
{
boolean odd = false;
for (char info : record.keySet())
{
if (record.get(info) % 2 != 0)
{
if (odd == false)
odd = true;
else
return false;
}
}
return true;
}

void getPath(TreeNode node, HashMap record)
{
if (node == null)
return;

if (record.containsKey(node.data))
record.put(node.data, record.get(node.data) + 1);
else
record.put(node.data, 1);

getPath(node.left, record);
getPath(node.right, record);

if (node.left == null && node.right == null)
{
if (isPalindrome(record))
result++;
}

if (record.get(node.data) == 1)
record.remove(node.data);
else
record.put(node.data, record.get(node.data) - 1);
}``````

## Algorithm Explanation

1. Implement a function `isPalindrome` that checks whether the permutation of characters in the path would result in a palindrome. It uses a `HashMap` to store character frequencies.
2. Implement a function `getPath` that recursively traverses the binary tree and maintains the character frequencies using the `record` map.
3. For each leaf node, call the `isPalindrome` function to check if the path forms a palindrome permutation.
4. If it does, increment the `result` counter.

## Code Solution

``````import java.util.HashMap;
/*
Java program
Count tree paths whose permutation is palindrome
*/
// 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 int result;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.result = 0;
}
public boolean isPalindrome(HashMap < Character, Integer > record)
{
boolean odd = false;
// Check that if given string can be palindrome
for (char info: record.keySet())
{
if (record.get(info) % 2 != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
public void getPath(TreeNode node, HashMap < Character, Integer > record)
{
if (node == null)
{
return;
}
if (record.containsKey(node.data))
{
// Increase node frequency
record.put(node.data, record.get(node.data) + 1);
}
else
{
// Add new node in record
record.put(node.data, 1);
}
// Visit left subtree
getPath(node.left, record);
// Visit right subtree
getPath(node.right, record);
if (node.left == null && node.right == null)
{
// When node is leaf node
if (isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
this.result++;
}
}
if (record.get(node.data) == 1)
{
// Remove the node from  record
record.remove(node.data);
}
else
{
record.put(node.data, record.get(node.data) - 1);
}
}
// Display inorder sequence in binary tree
public void printInorder(TreeNode node)
{
if (node == null)
{
return;
}
// Visit left subtree
printInorder(node.left);
// print node value
System.out.print("  " + node.data);
// Visit right subtree
printInorder(node.right);
}
public void palindromePath()
{
//Use to count frequency of path elements
HashMap < Character, Integer > record =
new HashMap < Character, Integer > ();
this.result = 0;
getPath(this.root, record);
// Display inorder of binary tree
printInorder(this.root);
// Display calculated result
System.out.println("\n Permutable palindromic paths is " + this.result);
}
public static void main(String[] args)
{
// Create new binary tree
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('a');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('c');
tree1.root.left.left = new TreeNode('a');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('a');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1.palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('a');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('a');
tree2.root.right = new TreeNode('h');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('h');
tree2.root.right.right.left = new TreeNode('b');
tree2.root.right.right.right.right = new TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2.palindromePath();
}
}``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````
``````// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;

/*
C++ program
Count tree paths whose permutation is palindrome
*/
// 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;
int result;
BinaryTree()
{
this->root = NULL;
this->result = 0;
}
bool isPalindrome(unordered_map < char, int > record)
{
bool odd = false;
// Check that if given string can be palindrome
for (auto &info: record)
{
if (info.second % 2 != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
void getPath(TreeNode *node, unordered_map < char, int > &record)
{
if (node == NULL)
{
return;
}
if (record.find(node->data) != record.end())
{
// Increase node frequency
record[node->data] = record[node->data] + 1;
}
else
{
// Add new node in record
record[node->data] = 1;
}
// Visit left subtree
this->getPath(node->left, record);
// Visit right subtree
this->getPath(node->right, record);
if (node->left == NULL && node->right == NULL)
{
// When node is leaf node
if (this->isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
this->result++;
}
}
if (record[node->data] == 1)
{
// Remove the node from  record
record.erase(node->data);
}
else
{
record[node->data] = record[node->data] - 1;
}
}
// Display inorder sequence in binary tree
void printInorder(TreeNode *node)
{
if (node == NULL)
{
return;
}
// Visit left subtree
this->printInorder(node->left);
// print node value
cout << "  " << node->data;
// Visit right subtree
this->printInorder(node->right);
}
void palindromePath()
{
//Use to count frequency of path elements
unordered_map < char, int > record ;
this->result = 0;
this->getPath(this->root, record);
// Display inorder of binary tree
this->printInorder(this->root);
// Display calculated result
cout << "\n Permutable palindromic paths is " << this->result << endl;
}
};
int main()
{
// Create new binary tree
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1->root = new TreeNode('a');
tree1->root->left = new TreeNode('c');
tree1->root->left->right = new TreeNode('a');
tree1->root->left->right->left = new TreeNode('d');
tree1->root->left->right->right = new TreeNode('c');
tree1->root->left->left = new TreeNode('a');
tree1->root->right = new TreeNode('e');
tree1->root->right->right = new TreeNode('a');
tree1->root->right->right->right = new TreeNode('b');
tree1->root->right->right->left = new TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1->palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2->root = new TreeNode('a');
tree2->root->left = new TreeNode('a');
tree2->root->left->right = new TreeNode('a');
tree2->root->left->right->left = new TreeNode('d');
tree2->root->left->right->right = new TreeNode('a');
tree2->root->right = new TreeNode('h');
tree2->root->right->right = new TreeNode('e');
tree2->root->right->right->right = new TreeNode('h');
tree2->root->right->right->left = new TreeNode('b');
tree2->root->right->right->right->right = new TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2->palindromePath();
return 0;
}``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program
Count tree paths whose permutation is palindrome
*/
// 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 int result;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.result = 0;
}
public Boolean isPalindrome(Dictionary < char, int > record)
{
Boolean odd = false;
// Check that if given string can be palindrome
foreach(KeyValuePair < char, int > info in record)
{
if (info.Value % 2 != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
public void getPath(TreeNode node, Dictionary < char, int > record)
{
if (node == null)
{
return;
}
if (record.ContainsKey(node.data))
{
// Increase node frequency
record[node.data] = record[node.data] + 1;
}
else
{
// Add new node in record
}
// Visit left subtree
this.getPath(node.left, record);
// Visit right subtree
this.getPath(node.right, record);
if (node.left == null && node.right == null)
{
// When node is leaf node
if (this.isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
this.result++;
}
}
if (record[node.data] == 1)
{
// Remove the node from  record
record.Remove(node.data);
}
else
{
record[node.data] = record[node.data] - 1;
}
}
// Display inorder sequence in binary tree
public void printInorder(TreeNode node)
{
if (node == null)
{
return;
}
// Visit left subtree
this.printInorder(node.left);
// print node value
Console.Write("  " + node.data);
// Visit right subtree
this.printInorder(node.right);
}
public void palindromePath()
{
//Use to count frequency of path elements
Dictionary < char, int > record = new Dictionary < char, int > ();
this.result = 0;
this.getPath(this.root, record);
// Display inorder of binary tree
this.printInorder(this.root);
// Display calculated result
Console.WriteLine("\n Permutable palindromic paths is " + this.result);
}
public static void Main(String[] args)
{
// Create new binary tree
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('a');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('c');
tree1.root.left.left = new TreeNode('a');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('a');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1.palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('a');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('a');
tree2.root.right = new TreeNode('h');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('h');
tree2.root.right.right.left = new TreeNode('b');
tree2.root.right.right.right.right = new TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2.palindromePath();
}
}``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````
``````<?php
/*
Php program
Count tree paths whose permutation is palindrome
*/
// 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 \$result;
public	function __construct()
{
\$this->root = NULL;
\$this->result = 0;
}
public	function isPalindrome(\$record)
{
\$odd = false;
// Check that if given string can be palindrome
foreach(\$record as \$key => \$value)
{
if (\$value % 2 != 0)
{
if (\$odd == false)
{
// One odd allow
\$odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
public	function getPath(\$node, &\$record)
{
if (\$node == NULL)
{
return;
}
if (array_key_exists(\$node->data, \$record))
{
// Increase node frequency
\$record[\$node->data] = \$record[\$node->data] + 1;
}
else
{
// Add new node in record
\$record[\$node->data] = 1;
}
// Visit left subtree
\$this->getPath(\$node->left, \$record);
// Visit right subtree
\$this->getPath(\$node->right, \$record);
if (\$node->left == NULL && \$node->right == NULL)
{
// When node is leaf node
if (\$this->isPalindrome(\$record))
{
// Increase the resultant counter
// When path are generated a palindrome
\$this->result++;
}
}
if (\$record[\$node->data] == 1)
{
// Remove the node from  record
unset(\$record[\$node->data]);
}
else
{
\$record[\$node->data] = \$record[\$node->data] - 1;
}
}
// Display inorder sequence in binary tree
public	function printInorder(\$node)
{
if (\$node == NULL)
{
return;
}
// Visit left subtree
\$this->printInorder(\$node->left);
// print node value
echo("  ".\$node->data);
// Visit right subtree
\$this->printInorder(\$node->right);
}
public	function palindromePath()
{
//Use to count frequency of path elements
\$record = array();
\$this->result = 0;
\$this->getPath(\$this->root, \$record);
// Display inorder of binary tree
\$this->printInorder(\$this->root);
// Display calculated result
echo("\n Permutable palindromic paths is ".\$this->result."\n");
}
}

function main()
{
// Create new binary tree
\$tree1 = new BinaryTree();
\$tree2 = new BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
\$tree1->root = new TreeNode('a');
\$tree1->root->left = new TreeNode('c');
\$tree1->root->left->right = new TreeNode('a');
\$tree1->root->left->right->left = new TreeNode('d');
\$tree1->root->left->right->right = new TreeNode('c');
\$tree1->root->left->left = new TreeNode('a');
\$tree1->root->right = new TreeNode('e');
\$tree1->root->right->right = new TreeNode('a');
\$tree1->root->right->right->right = new TreeNode('b');
\$tree1->root->right->right->left = new TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
\$tree1->palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
\$tree2->root = new TreeNode('a');
\$tree2->root->left = new TreeNode('a');
\$tree2->root->left->right = new TreeNode('a');
\$tree2->root->left->right->left = new TreeNode('d');
\$tree2->root->left->right->right = new TreeNode('a');
\$tree2->root->right = new TreeNode('h');
\$tree2->root->right->right = new TreeNode('e');
\$tree2->root->right->right->right = new TreeNode('h');
\$tree2->root->right->right->left = new TreeNode('b');
\$tree2->root->right->right->right->right = new TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
\$tree2->palindromePath();
}
main();``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````
``````/*
Node JS program
Count tree paths whose permutation is palindrome
*/
// 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;
this.result = 0;
}
isPalindrome(record)
{
var odd = false;
// Check that if given string can be palindrome
for (let [key, value] of record)
{
if (value % 2 != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
getPath(node, record)
{
if (node == null)
{
return;
}
if (record.has(node.data))
{
// Increase node frequency
record.set(node.data, record.get(node.data) + 1);
}
else
{
// Add new node in record
record.set(node.data, 1);
}
// Visit left subtree
this.getPath(node.left, record);
// Visit right subtree
this.getPath(node.right, record);
if (node.left == null && node.right == null)
{
// When node is leaf node
if (this.isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
this.result++;
}
}
if (record.get(node.data) == 1)
{
// Remove the node from  record
record.delete(node.data);
}
else
{
record.set(node.data, record.get(node.data) - 1);
}
}
// Display inorder sequence in binary tree
printInorder(node)
{
if (node == null)
{
return;
}
// Visit left subtree
this.printInorder(node.left);
// print node value
process.stdout.write("  " + node.data);
// Visit right subtree
this.printInorder(node.right);
}
palindromePath()
{
//Use to count frequency of path elements
var record = new Map();
this.result = 0;
this.getPath(this.root, record);
// Display inorder of binary tree
this.printInorder(this.root);
// Display calculated result
console.log("\n Permutable palindromic paths is " + this.result);
}
}

function main()
{
// Create new binary tree
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('a');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('c');
tree1.root.left.left = new TreeNode('a');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('a');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1.palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('a');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('a');
tree2.root.right = new TreeNode('h');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('h');
tree2.root.right.right.left = new TreeNode('b');
tree2.root.right.right.right.right = new TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2.palindromePath();
}
main();``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````
``````#  Python 3 program
#  Count tree paths whose permutation is palindrome

#  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
self.result = 0

def isPalindrome(self, record) :
odd = False
#  Check that if given string can be palindrome
for key, value in record.items() :
if (value % 2 != 0) :
if (odd == False) :
#  One odd allow
odd = True
else :
#  When have more than two odd character
return False

return True

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

if (node.data in record.keys()) :
#  Increase node frequency
record[node.data] = record.get(node.data) + 1
else :
#  Add new node in record
record[node.data] = 1

#  Visit left subtree
self.getPath(node.left, record)
#  Visit right subtree
self.getPath(node.right, record)
if (node.left == None and node.right == None) :
#  When node is leaf node
if (self.isPalindrome(record)) :
#  Increase the resultant counter
#  When path are generated a palindrome
self.result += 1

if (record.get(node.data) == 1) :
#  Remove the node from  record
del record[node.data]
else :
record[node.data] = record.get(node.data) - 1

#  Display inorder sequence in binary tree
def printInorder(self, node) :
if (node == None) :
return

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

def palindromePath(self) :
# Use to count frequency of path elements
record = dict()
self.result = 0
self.getPath(self.root, record)
#  Display inorder of binary tree
self.printInorder(self.root)
#  Display calculated result
print("\n Permutable palindromic paths is ", self.result)

def main() :
#  Create new binary tree
tree1 = BinaryTree()
tree2 = BinaryTree()
#     a
#    / \
#   /   \
#  c     e
# / \     \
# a   a     a
#   / \   / \
#  d   c e   b
# -----------------
# Constructing binary tree
tree1.root = TreeNode('a')
tree1.root.left = TreeNode('c')
tree1.root.left.right = TreeNode('a')
tree1.root.left.right.left = TreeNode('d')
tree1.root.left.right.right = TreeNode('c')
tree1.root.left.left = TreeNode('a')
tree1.root.right = TreeNode('e')
tree1.root.right.right = TreeNode('a')
tree1.root.right.right.right = TreeNode('b')
tree1.root.right.right.left = TreeNode('e')
#  Test A
#  a  c  a
#  a  c  c a  or c  a  a  c
#  a  e  e a  or e  a  a  e
#  Result : 3
tree1.palindromePath()
#     a
#    / \
#   /   \
#  a     h
#   \     \
#    a     e
#   / \   / \
#  d   a b   h
#             \
#              e
# -----------------
# Constructing binary tree
tree2.root = TreeNode('a')
tree2.root.left = TreeNode('a')
tree2.root.left.right = TreeNode('a')
tree2.root.left.right.left = TreeNode('d')
tree2.root.left.right.right = TreeNode('a')
tree2.root.right = TreeNode('h')
tree2.root.right.right = TreeNode('e')
tree2.root.right.right.right = TreeNode('h')
tree2.root.right.right.left = TreeNode('b')
tree2.root.right.right.right.right = TreeNode('e')
#  Test B
#  [a  a  a  a]
#  [h  e  a  e  h] or [e h a h e]
#  Result : 2
tree2.palindromePath()

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

#### input

``````   a   c   d   a   c   a   e   e   a   b
Permutable palindromic paths is  3
a   d   a   a   a   h   b   e   h   e
Permutable palindromic paths is  2``````
``````#  Ruby program
#  Count tree paths whose permutation is palindrome

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

end

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

def isPalindrome(record)
odd = false
#  Check that if given string can be palindrome
record.each { | key, value |
if (value % 2 != 0)
if (odd == false)
#  One odd allow
odd = true
else
#  When have more than two odd character
return false
end

end

}
return true
end

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

if (record.key?(node.data))
#  Increase node frequency
record[node.data] = record[node.data] + 1
else

#  Add new node in record
record[node.data] = 1
end

#  Visit left subtree
self.getPath(node.left, record)
#  Visit right subtree
self.getPath(node.right, record)
if (node.left == nil && node.right == nil)
#  When node is leaf node
if (self.isPalindrome(record))
#  Increase the resultant counter
#  When path are generated a palindrome
self.result += 1
end

end

if (record[node.data] == 1)
#  Remove the node from  record
record.delete(node.data)
else

record[node.data] = record[node.data] - 1
end

end

#  Display inorder sequence in binary tree
def printInorder(node)
if (node == nil)
return
end

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

def palindromePath()
# Use to count frequency of path elements
record = Hash.new()
self.result = 0
self.getPath(self.root, record)
#  Display inorder of binary tree
self.printInorder(self.root)
#  Display calculated result
print("\n Permutable palindromic paths is ", self.result, "\n")
end

end

def main()
#  Create new binary tree
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
#     a
#    / \
#   /   \
#  c     e
# / \     \
# a   a     a
#   / \   / \
#  d   c e   b
# -----------------
# Constructing binary tree
tree1.root = TreeNode.new('a')
tree1.root.left = TreeNode.new('c')
tree1.root.left.right = TreeNode.new('a')
tree1.root.left.right.left = TreeNode.new('d')
tree1.root.left.right.right = TreeNode.new('c')
tree1.root.left.left = TreeNode.new('a')
tree1.root.right = TreeNode.new('e')
tree1.root.right.right = TreeNode.new('a')
tree1.root.right.right.right = TreeNode.new('b')
tree1.root.right.right.left = TreeNode.new('e')
#  Test A
#  a  c  a
#  a  c  c a  or c  a  a  c
#  a  e  e a  or e  a  a  e
#  Result : 3
tree1.palindromePath()
#     a
#    / \
#   /   \
#  a     h
#   \     \
#    a     e
#   / \   / \
#  d   a b   h
#             \
#              e
# -----------------
# Constructing binary tree
tree2.root = TreeNode.new('a')
tree2.root.left = TreeNode.new('a')
tree2.root.left.right = TreeNode.new('a')
tree2.root.left.right.left = TreeNode.new('d')
tree2.root.left.right.right = TreeNode.new('a')
tree2.root.right = TreeNode.new('h')
tree2.root.right.right = TreeNode.new('e')
tree2.root.right.right.right = TreeNode.new('h')
tree2.root.right.right.left = TreeNode.new('b')
tree2.root.right.right.right.right = TreeNode.new('e')
#  Test B
#  [a  a  a  a]
#  [h  e  a  e  h] or [e h a h e]
#  Result : 2
tree2.palindromePath()
end

main()``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2
``````
``````import scala.collection.mutable._;
/*
Scala program
Count tree paths whose permutation is palindrome
*/
// 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,
var result: Int)
{
def this()
{
this( null, 0);
}
def isPalindrome(record: HashMap[Character, Int]): Boolean = {
var odd: Boolean = false;
// Check that if given string can be palindrome
for ( (key,value) <-  record)
{
if (value % 2 != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
def getPath(node: TreeNode, record: HashMap[Character, Int]): Unit = {
if (node == null)
{
return;
}
if (record.contains(node.data))
{
// Increase node frequency
}
else
{
// Add new node in record
}
// Visit left subtree
getPath(node.left, record);
// Visit right subtree
getPath(node.right, record);
if (node.left == null && node.right == null)
{
// When node is leaf node
if (isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
this.result += 1;
}
}
if (record.get(node.data).get == 1)
{
// Remove the node from  record
record.remove(node.data);
}
else
{
}
}
// Display inorder sequence in binary tree
def printInorder(node: TreeNode): Unit = {
if (node == null)
{
return;
}
// Visit left subtree
printInorder(node.left);
// print node value
print("  " + node.data);
// Visit right subtree
printInorder(node.right);
}
def palindromePath(): Unit = {
//Use to count frequency of path elements
var record: HashMap[Character, Int] = new HashMap[Character, Int]();
this.result = 0;
getPath(this.root, record);
// Display inorder of binary tree
printInorder(this.root);
// Display calculated result
println("\n Permutable palindromic paths is " + this.result);
}
}
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
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1.root = new TreeNode('a');
tree1.root.left = new TreeNode('c');
tree1.root.left.right = new TreeNode('a');
tree1.root.left.right.left = new TreeNode('d');
tree1.root.left.right.right = new TreeNode('c');
tree1.root.left.left = new TreeNode('a');
tree1.root.right = new TreeNode('e');
tree1.root.right.right = new TreeNode('a');
tree1.root.right.right.right = new TreeNode('b');
tree1.root.right.right.left = new TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1.palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2.root = new TreeNode('a');
tree2.root.left = new TreeNode('a');
tree2.root.left.right = new TreeNode('a');
tree2.root.left.right.left = new TreeNode('d');
tree2.root.left.right.right = new TreeNode('a');
tree2.root.right = new TreeNode('h');
tree2.root.right.right = new TreeNode('e');
tree2.root.right.right.right = new TreeNode('h');
tree2.root.right.right.left = new TreeNode('b');
tree2.root.right.right.right.right = new TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2.palindromePath();
}
}``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````
``````import Foundation;
/*
Swift 4 program
Count tree paths whose permutation is palindrome
*/

// 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? ;
var result: Int;
init()
{
self.root = nil;
self.result = 0;
}
func isPalindrome(_ record: [Character : Int]) -> Bool
{
var odd = false;
// Check that if given string can be palindrome
for (_, value) in record
{
if (value % 2  != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
func getPath(_ node: TreeNode? , _ record : inout[Character : Int])
{
if (node == nil)
{
return;
}
if (record.keys.contains(node!.data))
{
// Increase node frequency
record[node!.data] = record[node!.data]! + 1;
}
else
{
// Add new node in record
record[node!.data] = 1;
}
// Visit left subtree
self.getPath(node!.left, &record);
// Visit right subtree
self.getPath(node!.right, &record);
if (node!.left == nil && node!.right == nil)
{
// When node is leaf node
if (self.isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
self.result += 1;
}
}
if (record[node!.data] == 1)
{
// Remove the node from  record
record.removeValue(forKey: node!.data);
}
else
{
record[node!.data] = record[node!.data]! - 1;
}
}
// Display inorder sequence in binary tree
func printInorder(_ node: TreeNode? )
{
if (node == nil)
{
return;
}
// Visit left subtree
self.printInorder(node!.left);
// print node value
print("  ", node!.data, terminator: "");
// Visit right subtree
self.printInorder(node!.right);
}
func palindromePath()
{
//Use to count frequency of path elements
var record = [Character : Int]();
self.result = 0;
self.getPath(self.root, &record);
// Display inorder of binary tree
self.printInorder(self.root);
// Display calculated result
print("\n Permutable palindromic paths is ", self.result);
}
}
func main()
{
// Create new binary tree
let tree1 = BinaryTree();
let tree2 = BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1.root = TreeNode("a");
tree1.root!.left = TreeNode("c");
tree1.root!.left!.right = TreeNode("a");
tree1.root!.left!.right!.left = TreeNode("d");
tree1.root!.left!.right!.right = TreeNode("c");
tree1.root!.left!.left = TreeNode("a");
tree1.root!.right = TreeNode("e");
tree1.root!.right!.right = TreeNode("a");
tree1.root!.right!.right!.right = TreeNode("b");
tree1.root!.right!.right!.left = TreeNode("e");
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1.palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2.root = TreeNode("a");
tree2.root!.left = TreeNode("a");
tree2.root!.left!.right = TreeNode("a");
tree2.root!.left!.right!.left = TreeNode("d");
tree2.root!.left!.right!.right = TreeNode("a");
tree2.root!.right = TreeNode("h");
tree2.root!.right!.right = TreeNode("e");
tree2.root!.right!.right!.right = TreeNode("h");
tree2.root!.right!.right!.left = TreeNode("b");
tree2.root!.right!.right!.right!.right = TreeNode("e");
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2.palindromePath();
}
main();``````

#### input

``````   a   c   d   a   c   a   e   e   a   b
Permutable palindromic paths is  3
a   d   a   a   a   h   b   e   h   e
Permutable palindromic paths is  2``````
``````/*
Kotlin program
Count tree paths whose permutation is palindrome
*/
// 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 ? ;
var result: Int;
constructor()
{
this.root = null;
this.result = 0;
}
fun isPalindrome(record: MutableMap < Char, Int > ): Boolean
{
var odd: Boolean = false;
// Check that if given string can be palindrome
for ((_, value) in record)
{
if (value % 2 != 0)
{
if (odd == false)
{
// One odd allow
odd = true;
}
else
{
// When have more than two odd character
return false;
}
}
}
return true;
}
fun getPath(node: TreeNode ? , record : MutableMap < Char, Int >): Unit
{
if (node == null)
{
return;
}
if (record.containsKey(node.data))
{
// Increase node frequency
record.put(node.data, record.getValue(node.data) + 1);
}
else
{
// Add new node in record
record.put(node.data, 1);
}
// Visit left subtree
this.getPath(node.left, record);
// Visit right subtree
this.getPath(node.right, record);
if (node.left == null && node.right == null)
{
// When node is leaf node
if (this.isPalindrome(record))
{
// Increase the resultant counter
// When path are generated a palindrome
this.result += 1;
}
}
if (record.getValue(node.data) == 1)
{
// Remove the node from  record
record.remove(node.data);
}
else
{
record.put(node.data, record.getValue(node.data) - 1);
}
}
// Display inorder sequence in binary tree
fun printInorder(node: TreeNode ? ): Unit
{
if (node == null)
{
return;
}
// Visit left subtree
this.printInorder(node.left);
// print node value
print("  " + node.data);
// Visit right subtree
this.printInorder(node.right);
}
fun palindromePath(): Unit
{
// Use to count frequency of path elements
val record = mutableMapOf < Char , Int > ();
this.result = 0;
this.getPath(this.root, record);
// Display inorder of binary tree
this.printInorder(this.root);
// Display calculated result
println("\n Permutable palindromic paths is " + this.result);
}
}
fun main(args: Array < String > ): Unit
{
// Create new binary tree
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
/*
a
/ \
/   \
c     e
/ \     \
a   a     a
/ \   / \
d   c e   b
-----------------
Constructing binary tree
*/
tree1.root = TreeNode('a');
tree1.root?.left = TreeNode('c');
tree1.root?.left?.right = TreeNode('a');
tree1.root?.left?.right?.left = TreeNode('d');
tree1.root?.left?.right?.right = TreeNode('c');
tree1.root?.left?.left = TreeNode('a');
tree1.root?.right = TreeNode('e');
tree1.root?.right?.right = TreeNode('a');
tree1.root?.right?.right?.right = TreeNode('b');
tree1.root?.right?.right?.left = TreeNode('e');
// Test A
// a  c  a
// a  c  c a  or c  a  a  c
// a  e  e a  or e  a  a  e
// Result : 3
tree1.palindromePath();
/*
a
/ \
/   \
a     h
\     \
a     e
/ \   / \
d   a b   h
\
e
-----------------
Constructing binary tree
*/
tree2.root = TreeNode('a');
tree2.root?.left = TreeNode('a');
tree2.root?.left?.right = TreeNode('a');
tree2.root?.left?.right?.left = TreeNode('d');
tree2.root?.left?.right?.right = TreeNode('a');
tree2.root?.right = TreeNode('h');
tree2.root?.right?.right = TreeNode('e');
tree2.root?.right?.right?.right = TreeNode('h');
tree2.root?.right?.right?.left = TreeNode('b');
tree2.root?.right?.right?.right?.right = TreeNode('e');
// Test B
// [a  a  a  a]
// [h  e  a  e  h] or [e h a h e]
// Result : 2
tree2.palindromePath();
}``````

#### input

``````  a  c  d  a  c  a  e  e  a  b
Permutable palindromic paths is 3
a  d  a  a  a  h  b  e  h  e
Permutable palindromic paths is 2``````

## Output Explanation

The code implements the algorithm and calculates the number of paths in the binary tree where the permutation of nodes along the path forms a palindrome. It displays the tree nodes using an in-order traversal and prints the calculated result.

## 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 visit each node exactly once during the traversal. The space complexity is also O(N) due to the space required for the `HashMap` to store character frequencies.

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