Skip to main content

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
			record.Add(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.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_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, :result
	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
			record.addOne(node.data, record.get(node.data).get + 1);
		}
		else
		{
			// Add new node in record
			record.addOne(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 += 1;
			}
		}
		if (record.get(node.data).get == 1)
		{
			// Remove the node from  record
			record.remove(node.data);
		}
		else
		{
			record.addOne(node.data, record.get(node.data).get - 1);
		}
	}
	// 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.

Last updated on by Kalkicode




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