Posted on by Kalkicode
Code Binary Tree

Print all palindromic paths of binary tree

Here given code implementation process.

/*
    C Program 
    Print all palindromic paths of binary tree
*/
#include <stdio.h>

#include <stdlib.h>

// Tree Node
struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
    struct TreeNode *root;
};
// Create new tree
struct BinaryTree *new_tree()
{
    // Create dynamic node
    struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    //return new tree
    return tree;
}
// returns a new node of tree
struct TreeNode *new_node(int data)
{
    // Create dynamic node
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        //Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        //This is indicates, segmentation fault or memory overflow problem
        printf("Memory Overflow\n");
    }
    //return new node
    return node;
}
// This are check whether given path contains palindrome or not
int isPalindrom(int auxiliary[], int length)
{
    int a = 0;
    int b = length;
    while (a < b)
    {
        if (auxiliary[a] != auxiliary[b])
        {
            return 0;
        }
        // Update element location
        a++;
        b--;
    }
    // When palindrome exists
    return 1;
}
// This function are printing given path which is contain palindromes
void printPath(int auxiliary[], int size)
{
    for (int i = 0; i <= size; ++i)
    {
        // Display node value
        printf("  %d", auxiliary[i]);
    }
    printf("\n");
}
// Collect all paths from root to leaf nodes
// And path contains palindrome then this are request to print resultant data
void findPath(struct TreeNode *node, int auxiliary[], int location)
{
    if (node != NULL)
    {
        auxiliary[location] = node->data;
        if (node->left == NULL && node->right == NULL)
        {
            if (isPalindrom(auxiliary, location))
            {
                // When palindrome exist
                printPath(auxiliary, location);
            }
            return;
        }
        // Collecting path through by recursion
        findPath(node->left, auxiliary, location + 1);
        findPath(node->right, auxiliary, location + 1);
    }
}
//Find height of given binary tree
int height(struct TreeNode *root)
{
    if (root != NULL)
    {
        int a = height(root->left);
        int b = height(root->right);
        //returning a height of largest subtree
        if (a > b)
        {
            return a + 1;
        }
        else
        {
            return b + 1;
        }
    }
    return 0;
}
void palindromicPath(struct TreeNode *root)
{
    int size = height(root);
    // auxiliary space which is used to collect path
    int auxiliary[size];
    findPath(root, auxiliary, 0);
}
int main()
{
    struct BinaryTree *tree = new_tree();
    /*
            4
           / \
          5   7
         / \   \
        5   3   7
       /   / \   \
      4   4   5   4
             / \
            1   4
    -----------------------
        Binary Tree
    */
    tree->root = new_node(4);
    tree->root->left = new_node(5);
    tree->root->right = new_node(7);
    tree->root->left->left = new_node(5);
    tree->root->left->left->left = new_node(4);
    tree->root->left->right = new_node(3);
    tree->root->left->right->left = new_node(4);
    tree->root->left->right->right = new_node(5);
    tree->root->left->right->right->left = new_node(5);
    tree->root->left->right->right->right = new_node(4);
    tree->root->right->right = new_node(7);
    tree->root->right->right->right = new_node(4);
    palindromicPath(tree->root);
    return 0;
}

Output

  4  5  5  4
  4  5  3  5  4
  4  7  7  4
/*
    Java Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	// This are check whether given path contains palindrome or not
	public boolean isPalindrom(int[] auxiliary, int length)
	{
		int a = 0;
		int b = length;
		while (a < b)
		{
			if (auxiliary[a] != auxiliary[b])
			{
				return false;
			}
			// Update element location
			a++;
			b--;
		}
		// When palindrome exists
		return true;
	}
	// This function are printing given path which is contain palindromes
	public void printPath(int[] auxiliary, int size)
	{
		for (int i = 0; i <= size; ++i)
		{
			// Display node value
			System.out.print(" " + auxiliary[i]);
		}
		System.out.print("\n");
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	public void findPath(TreeNode node, int[] auxiliary, int location)
	{
		if (node != null)
		{
			auxiliary[location] = node.data;
			if (node.left == null && node.right == null)
			{
				if (isPalindrom(auxiliary, location))
				{
					// When palindrome exist
					printPath(auxiliary, location);
				}
				return;
			}
			// Collecting path through by recursion
			findPath(node.left, auxiliary, location + 1);
			findPath(node.right, auxiliary, location + 1);
		}
	}
	//Find height of given binary tree
	public int height(TreeNode root)
	{
		if (root != null)
		{
			int a = height(root.left);
			int b = height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		return 0;
	}
	public void palindromicPath(TreeNode root)
	{
		int size = height(root);
		if (size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		int[] auxiliary = new int[size];
		findPath(root, auxiliary, 0);
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		        4
		       / \
		      5   7
		     / \   \
		    5   3   7
		   /   / \   \
		  4   4   5   4
		         / \
		        1   4
		-----------------------
		    Binary Tree
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(5);
		tree.root.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(5);
		tree.root.left.left.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(4);
		tree.root.left.right.right = new TreeNode(5);
		tree.root.left.right.right.left = new TreeNode(5);
		tree.root.left.right.right.right = new TreeNode(4);
		tree.root.right.right = new TreeNode(7);
		tree.root.right.right.right = new TreeNode(4);
		tree.palindromicPath(tree.root);
	}
}

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
// Binary Tree
class BinaryTree
{
	public: TreeNode *root;
	BinaryTree()
	{
		this->root = NULL;
	}
	// This are check whether given path contains palindrome or not
	bool isPalindrom(int auxiliary[], int length)
	{
		// When palindrome exists
		int a = 0;
		int b = length;
		while (a < b)
		{
			if (auxiliary[a] != auxiliary[b])
			{
				return false;
			}
			// Update element location
			a++;
			b--;
		}
		return true;
	}
	// This function are printing given path which is contain palindromes
	void printPath(int auxiliary[], int size)
	{
		for (int i = 0; i <= size; ++i)
		{
			// Display node value
			cout << " " << auxiliary[i];
		}
		cout << "\n";
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	void findPath(TreeNode *node, int auxiliary[], int location)
	{
		if (node != NULL)
		{
			auxiliary[location] = node->data;
			if (node->left == NULL && node->right == NULL)
			{
				if (this->isPalindrom(auxiliary, location))
				{
					// When palindrome exist
					this->printPath(auxiliary, location);
				}
				return;
			}
			// Collecting path through by recursion
			this->findPath(node->left, auxiliary, location + 1);
			this->findPath(node->right, auxiliary, location + 1);
		}
	}
	//Find height of given binary tree
	int height(TreeNode *root)
	{
		if (root != NULL)
		{
			int a = this->height(root->left);
			int b = this->height(root->right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		return 0;
	}
	void palindromicPath(TreeNode *root)
	{
		int size = this->height(root);
		if (size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		int auxiliary[size];
		this->findPath(root, auxiliary, 0);
	}
};
int main()
{
	BinaryTree tree = BinaryTree();
	/*    4
	       / \
	      5   7
	     / \   \
	    5   3   7
	   /   / \   \
	  4   4   5   4
	         / \
	        1   4
	-----------------------
	    Binary Tree

	*/
	tree.root = new TreeNode(4);
	tree.root->left = new TreeNode(5);
	tree.root->right = new TreeNode(7);
	tree.root->left->left = new TreeNode(5);
	tree.root->left->left->left = new TreeNode(4);
	tree.root->left->right = new TreeNode(3);
	tree.root->left->right->left = new TreeNode(4);
	tree.root->left->right->right = new TreeNode(5);
	tree.root->left->right->right->left = new TreeNode(5);
	tree.root->left->right->right->right = new TreeNode(4);
	tree.root->right->right = new TreeNode(7);
	tree.root->right->right->right = new TreeNode(4);
	tree.palindromicPath(tree.root);
	return 0;
}

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4
// Include namespace system
using System;
/*
    C# Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	// This are check whether given path contains palindrome or not
	public Boolean isPalindrom(int[] auxiliary, int length)
	{
		// When palindrome exists
		int a = 0;
		int b = length;
		while (a < b)
		{
			if (auxiliary[a] != auxiliary[b])
			{
				return false;
			}
			// Update element location
			a++;
			b--;
		}
		return true;
	}
	// This function are printing given path which is contain palindromes
	public void printPath(int[] auxiliary, int size)
	{
		for (int i = 0; i <= size; ++i)
		{
			// Display node value
			Console.Write(" " + auxiliary[i]);
		}
		Console.Write("\n");
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	public void findPath(TreeNode node, int[] auxiliary, int location)
	{
		if (node != null)
		{
			auxiliary[location] = node.data;
			if (node.left == null && node.right == null)
			{
				if (isPalindrom(auxiliary, location))
				{
					// When palindrome exist
					printPath(auxiliary, location);
				}
				return;
			}
			// Collecting path through by recursion
			findPath(node.left, auxiliary, location + 1);
			findPath(node.right, auxiliary, location + 1);
		}
	}
	//Find height of given binary tree
	public int height(TreeNode root)
	{
		if (root != null)
		{
			int a = height(root.left);
			int b = height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		return 0;
	}
	public void palindromicPath(TreeNode root)
	{
		int size = height(root);
		if (size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		int[] auxiliary = new int[size];
		findPath(root, auxiliary, 0);
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*      4
		       / \
		      5   7
		     / \   \
		    5   3   7
		   /   / \   \
		  4   4   5   4
		         / \
		        1   4
		-----------------------
		    Binary Tree

		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(5);
		tree.root.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(5);
		tree.root.left.left.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(4);
		tree.root.left.right.right = new TreeNode(5);
		tree.root.left.right.right.left = new TreeNode(5);
		tree.root.left.right.right.right = new TreeNode(4);
		tree.root.right.right = new TreeNode(7);
		tree.root.right.right.right = new TreeNode(4);
		tree.palindromicPath(tree.root);
	}
}

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4
<?php
/*
    Php Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
// Binary Tree
class BinaryTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	// This are check whether given path contains palindrome or not
	public	function isPalindrom( & $auxiliary, $length)
	{
		// When palindrome exists
		$a = 0;
		$b = $length;
		while ($a < $b)
		{
			if ($auxiliary[$a] != $auxiliary[$b])
			{
				return false;
			}
			// Update element location
			$a++;
			$b--;
		}
		return true;
	}
	// This function are printing given path which is contain palindromes
	public	function printPath( & $auxiliary, $size)
	{
		for ($i = 0; $i <= $size; ++$i)
		{
			// Display node value
			echo " ". $auxiliary[$i];
		}
		echo "\n";
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	public	function findPath($node, & $auxiliary, $location)
	{
		if ($node != null)
		{
			$auxiliary[$location] = $node->data;
			if ($node->left == null && $node->right == null)
			{
				if ($this->isPalindrom($auxiliary, $location))
				{
					// When palindrome exist
					$this->printPath($auxiliary, $location);
				}
				return;
			}
			// Collecting path through by recursion
			$this->findPath($node->left, $auxiliary, $location + 1);
			$this->findPath($node->right, $auxiliary, $location + 1);
		}
	}
	//Find height of given binary tree
	public	function height($root)
	{
		if ($root != null)
		{
			$a = $this->height($root->left);
			$b = $this->height($root->right);
			//returning a height of largest subtree
			if ($a > $b)
			{
				return $a + 1;
			}
			else
			{
				return $b + 1;
			}
		}
		return 0;
	}
	public	function palindromicPath($root)
	{
		$size = $this->height($root);
		if ($size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		$auxiliary = array_fill(0, $size, 0);
		$this->findPath($root, $auxiliary, 0);
	}
}

function main()
{
	$tree = new BinaryTree();
	/*      4
	       / \
	      5   7
	     / \   \
	    5   3   7
	   /   / \   \
	  4   4   5   4
	         / \
	        1   4
	-----------------------
	    Binary Tree

	*/
	$tree->root = new TreeNode(4);
	$tree->root->left = new TreeNode(5);
	$tree->root->right = new TreeNode(7);
	$tree->root->left->left = new TreeNode(5);
	$tree->root->left->left->left = new TreeNode(4);
	$tree->root->left->right = new TreeNode(3);
	$tree->root->left->right->left = new TreeNode(4);
	$tree->root->left->right->right = new TreeNode(5);
	$tree->root->left->right->right->left = new TreeNode(5);
	$tree->root->left->right->right->right = new TreeNode(4);
	$tree->root->right->right = new TreeNode(7);
	$tree->root->right->right->right = new TreeNode(4);
	$tree->palindromicPath($tree->root);
}
main();

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4
/*
    Node Js Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Binary Tree
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	// This are check whether given path contains palindrome or not
	isPalindrom(auxiliary, length)
	{
		// When palindrome exists
		var a = 0;
		var b = length;
		while (a < b)
		{
			if (auxiliary[a] != auxiliary[b])
			{
				return false;
			}
			// Update element location
			a++;
			b--;
		}
		return true;
	}
	// This function are printing given path which is contain palindromes
	printPath(auxiliary, size)
	{
		for (var i = 0; i <= size; ++i)
		{
			// Display node value
			process.stdout.write(" " + auxiliary[i]);
		}
		process.stdout.write("\n");
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	findPath(node, auxiliary, location)
	{
		if (node != null)
		{
			auxiliary[location] = node.data;
			if (node.left == null && node.right == null)
			{
				if (this.isPalindrom(auxiliary, location))
				{
					// When palindrome exist
					this.printPath(auxiliary, location);
				}
				return;
			}
			// Collecting path through by recursion
			this.findPath(node.left, auxiliary, location + 1);
			this.findPath(node.right, auxiliary, location + 1);
		}
	}
	//Find height of given binary tree
	height(root)
	{
		if (root != null)
		{
			var a = this.height(root.left);
			var b = this.height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		return 0;
	}
	palindromicPath(root)
	{
		var size = this.height(root);
		if (size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		var auxiliary = Array(size).fill(0);
		this.findPath(root, auxiliary, 0);
	}
}

function main()
{
	var tree = new BinaryTree();
	/*      4
	       / \
	      5   7
	     / \   \
	    5   3   7
	   /   / \   \
	  4   4   5   4
	         / \
	        1   4
	-----------------------
	    Binary Tree

	*/
	tree.root = new TreeNode(4);
	tree.root.left = new TreeNode(5);
	tree.root.right = new TreeNode(7);
	tree.root.left.left = new TreeNode(5);
	tree.root.left.left.left = new TreeNode(4);
	tree.root.left.right = new TreeNode(3);
	tree.root.left.right.left = new TreeNode(4);
	tree.root.left.right.right = new TreeNode(5);
	tree.root.left.right.right.left = new TreeNode(5);
	tree.root.left.right.right.right = new TreeNode(4);
	tree.root.right.right = new TreeNode(7);
	tree.root.right.right.right = new TreeNode(4);
	tree.palindromicPath(tree.root);
}
main();

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4
#  Python 3 Program 
#  Print all palindromic paths of binary tree

#  Tree Node
class TreeNode :
	
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

#  Binary Tree
class BinaryTree :
	
	def __init__(self) :
		self.root = None
	
	#  This are check whether given path contains palindrome or not
	def isPalindrom(self, auxiliary, length) :
		#  When palindrome exists
		a = 0
		b = length
		while (a < b) :
			if (auxiliary[a] != auxiliary[b]) :
				return False
			
			#  Update element location
			a += 1
			b -= 1
		
		return True
	
	#  This function are printing given path which is contain palindromes
	def printPath(self, auxiliary, size) :
		i = 0
		while (i <= size) :
			#  Display node value
			print(" ", auxiliary[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Collect all paths from root to leaf nodes
	#  And path contains palindrome then this are request to print resultant data
	def findPath(self, node, auxiliary, location) :
		if (node != None) :
			auxiliary[location] = node.data
			if (node.left == None and node.right == None) :
				if (self.isPalindrom(auxiliary, location)) :
					#  When palindrome exist
					self.printPath(auxiliary, location)
				
				return
			
			#  Collecting path through by recursion
			self.findPath(node.left, auxiliary, location + 1)
			self.findPath(node.right, auxiliary, location + 1)
		
	
	# Find height of given binary tree
	def height(self, root) :
		if (root != None) :
			a = self.height(root.left)
			b = self.height(root.right)
			# returning a height of largest subtree
			if (a > b) :
				return a + 1
			else :
				return b + 1
			
		
		return 0
	
	def palindromicPath(self, root) :
		size = self.height(root)
		if (size == 0) :
			return
		
		#  auxiliary space which is used to collect path
		auxiliary = [0] * (size)
		self.findPath(root, auxiliary, 0)
	

def main() :
	tree = BinaryTree()
	#       4
	#        / \
	#       5   7
	#      / \   \
	#     5   3   7
	#    /   / \   \
	#   4   4   5   4
	#          / \
	#         1   4
	# -----------------------
	#     Binary Tree
	
	tree.root = TreeNode(4)
	tree.root.left = TreeNode(5)
	tree.root.right = TreeNode(7)
	tree.root.left.left = TreeNode(5)
	tree.root.left.left.left = TreeNode(4)
	tree.root.left.right = TreeNode(3)
	tree.root.left.right.left = TreeNode(4)
	tree.root.left.right.right = TreeNode(5)
	tree.root.left.right.right.left = TreeNode(5)
	tree.root.left.right.right.right = TreeNode(4)
	tree.root.right.right = TreeNode(7)
	tree.root.right.right.right = TreeNode(4)
	tree.palindromicPath(tree.root)

if __name__ == "__main__": main()

Output

  4  5  5  4
  4  5  3  5  4
  4  7  7  4
#   Ruby Program 
#   Print all palindromic paths of binary tree

#  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) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

#  Binary Tree
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		self.root = nil
	end

	#  This are check whether given path contains palindrome or not
	def isPalindrom(auxiliary, length) 
		#  When palindrome exists
		a = 0
		b = length
		while (a < b) 
			if (auxiliary[a] != auxiliary[b]) 
				return false
			end

			#  Update element location
			a += 1
			b -= 1
		end

		return true
	end

	#  This function are printing given path which is contain palindromes
	def printPath(auxiliary, size) 
		i = 0
		while (i <= size) 
			#  Display node value
			print(" ", auxiliary[i])
			i += 1
		end

		print("\n")
	end

	#  Collect all paths from root to leaf nodes
	#  And path contains palindrome then this are request to print resultant data
	def findPath(node, auxiliary, location) 
		if (node != nil) 
			auxiliary[location] = node.data
			if (node.left == nil && node.right == nil) 
				if (self.isPalindrom(auxiliary, location)) 
					#  When palindrome exist
					self.printPath(auxiliary, location)
				end

				return
			end

			#  Collecting path through by recursion
			self.findPath(node.left, auxiliary, location + 1)
			self.findPath(node.right, auxiliary, location + 1)
		end

	end

	# Find height of given binary tree
	def height(root) 
		if (root != nil) 
			a = self.height(root.left)
			b = self.height(root.right)
			# returning a height of largest subtree
			if (a > b) 
				return a + 1
			else 
				return b + 1
			end

		end

		return 0
	end

	def palindromicPath(root) 
		size = self.height(root)
		if (size == 0) 
			return
		end

		#  auxiliary space which is used to collect path
		auxiliary = Array.new(size) {0}
		self.findPath(root, auxiliary, 0)
	end

end

def main() 
	tree = BinaryTree.new()
	#       4
	#        / \
	#       5   7
	#      / \   \
	#     5   3   7
	#    /   / \   \
	#   4   4   5   4
	#          / \
	#         1   4
	# -----------------------
	#     Binary Tree
	
	tree.root = TreeNode.new(4)
	tree.root.left = TreeNode.new(5)
	tree.root.right = TreeNode.new(7)
	tree.root.left.left = TreeNode.new(5)
	tree.root.left.left.left = TreeNode.new(4)
	tree.root.left.right = TreeNode.new(3)
	tree.root.left.right.left = TreeNode.new(4)
	tree.root.left.right.right = TreeNode.new(5)
	tree.root.left.right.right.left = TreeNode.new(5)
	tree.root.left.right.right.right = TreeNode.new(4)
	tree.root.right.right = TreeNode.new(7)
	tree.root.right.right.right = TreeNode.new(4)
	tree.palindromicPath(tree.root)
end

main()

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4

/*
    Scala Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Binary Tree
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	// This are check whether given path contains palindrome or not
	def isPalindrom(auxiliary: Array[Int], length: Int): Boolean = {
		// When palindrome exists
		var a: Int = 0;
		var b: Int = length;
		while (a < b)
		{
			if (auxiliary(a) != auxiliary(b))
			{
				return false;
			}
			// Update element location
			a += 1;
			b -= 1;
		}
		return true;
	}
	// This function are printing given path which is contain palindromes
	def printPath(auxiliary: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i <= size)
		{
			// Display node value
			print(" " + auxiliary(i));
			i += 1;
		}
		print("\n");
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	def findPath(node: TreeNode, auxiliary: Array[Int], location: Int): Unit = {
		if (node != null)
		{
			auxiliary(location) = node.data;
			if (node.left == null && node.right == null)
			{
				if (this.isPalindrom(auxiliary, location))
				{
					// When palindrome exist
					this.printPath(auxiliary, location);
				}
				return;
			}
			// Collecting path through by recursion
			this.findPath(node.left, auxiliary, location + 1);
			this.findPath(node.right, auxiliary, location + 1);
		}
	}
	//Find height of given binary tree
	def height(root: TreeNode): Int = {
		if (root != null)
		{
			var a: Int = this.height(root.left);
			var b: Int = this.height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		return 0;
	}
	def palindromicPath(root: TreeNode): Unit = {
		var size: Int = this.height(root);
		if (size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		var auxiliary: Array[Int] = Array.fill[Int](size)(0);
		this.findPath(root, auxiliary, 0);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*      4
		       / \
		      5   7
		     / \   \
		    5   3   7
		   /   / \   \
		  4   4   5   4
		         / \
		        1   4
		-----------------------
		    Binary Tree

		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(5);
		tree.root.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(5);
		tree.root.left.left.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(4);
		tree.root.left.right.right = new TreeNode(5);
		tree.root.left.right.right.left = new TreeNode(5);
		tree.root.left.right.right.right = new TreeNode(4);
		tree.root.right.right = new TreeNode(7);
		tree.root.right.right.right = new TreeNode(4);
		tree.palindromicPath(tree.root);
	}
}

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4
/*
    Swift 4 Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
// Binary Tree
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// This are check whether given path contains palindrome or not
	func isPalindrom(_ auxiliary: [Int], _ length: Int)->Bool
	{
		// When palindrome exists
		var a: Int = 0;
		var b: Int = length;
		while (a < b)
		{
			if (auxiliary[a]  != auxiliary[b])
			{
				return false;
			}
			// Update element location
			a += 1;
			b -= 1;
		}
		return true;
	}
	// This function are printing given path which is contain palindromes
	func printPath(_ auxiliary: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i <= size)
		{
			// Display node value
			print(" ", auxiliary[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Collect all paths from root to leaf nodes
	// And path contains palindrome then this are request to print resultant data
	func findPath(_ node: TreeNode? , _ auxiliary : inout[Int], _ location: Int)
	{
		if (node  != nil)
		{
			auxiliary[location] = node!.data;
			if (node!.left == nil && node!.right == nil)
			{
				if (self.isPalindrom(auxiliary, location))
				{
					// When palindrome exist
					self.printPath(auxiliary, location);
				}
				return;
			}
			// Collecting path through by recursion
			self.findPath(node!.left, &auxiliary, location + 1);
			self.findPath(node!.right, &auxiliary, location + 1);
		}
	}
	//Find height of given binary tree
	func height(_ root: TreeNode? )->Int
	{
		if (root  != nil)
		{
			let a: Int = self.height(root!.left);
			let b: Int = self.height(root!.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		return 0;
	}
	func palindromicPath(_ root: TreeNode? )
	{
		let size: Int = self.height(root);
		if (size == 0)
		{
			return;
		}
		// auxiliary space which is used to collect path
		var auxiliary: [Int] = Array(repeating: 0, count: size);
		self.findPath(root, &auxiliary, 0);
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*      4
	       / \
	      5   7
	     / \   \
	    5   3   7
	   /   / \   \
	  4   4   5   4
	         / \
	        1   4
	-----------------------
	    Binary Tree

	*/
	tree.root = TreeNode(4);
	tree.root!.left = TreeNode(5);
	tree.root!.right = TreeNode(7);
	tree.root!.left!.left = TreeNode(5);
	tree.root!.left!.left!.left = TreeNode(4);
	tree.root!.left!.right = TreeNode(3);
	tree.root!.left!.right!.left = TreeNode(4);
	tree.root!.left!.right!.right = TreeNode(5);
	tree.root!.left!.right!.right!.left = TreeNode(5);
	tree.root!.left!.right!.right!.right = TreeNode(4);
	tree.root!.right!.right = TreeNode(7);
	tree.root!.right!.right!.right = TreeNode(4);
	tree.palindromicPath(tree.root);
}
main();

Output

  4  5  5  4
  4  5  3  5  4
  4  7  7  4
/*
    Kotlin Program 
    Print all palindromic paths of binary tree
*/
// Tree Node
class TreeNode
{
    var data: Int;
    var left: TreeNode ? ;
    var right: TreeNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
// Binary Tree
class BinaryTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = null;
    }
    // This are check whether given path contains palindrome or not
    fun isPalindrom(auxiliary: Array < Int > , length: Int): Boolean
    {
        // When palindrome exists
        var a: Int = 0;
        var b: Int = length;
        while (a < b)
        {
            if (auxiliary[a] != auxiliary[b])
            {
                return false;
            }
            // Update element location
            a += 1;
            b -= 1;
        }
        return true;
    }
    // This function are printing given path which is contain palindromes
    fun printPath(auxiliary: Array < Int > , size: Int): Unit
    {
        var i: Int = 0;
        while (i <= size)
        {
            // Display node value
            print(" " + auxiliary[i]);
            i += 1;
        }
        print("\n");
    }
    // Collect all paths from root to leaf nodes
    // And path contains palindrome then this are request to print resultant data
    fun findPath(node: TreeNode ? , auxiliary : Array < Int > , location: Int): Unit
    {
        if (node != null)
        {
            auxiliary[location] = node.data;
            if (node.left == null && node.right == null)
            {
                if (this.isPalindrom(auxiliary, location))
                {
                    // When palindrome exist
                    this.printPath(auxiliary, location);
                }
                return;
            }
            // Collecting path through by recursion
            this.findPath(node.left, auxiliary, location + 1);
            this.findPath(node.right, auxiliary, location + 1);
        }
    }
    //Find height of given binary tree
    fun height(root: TreeNode ? ): Int
    {
        if (root != null)
        {
            var a: Int = this.height(root.left);
            var b: Int = this.height(root.right);
            //returning a height of largest subtree
            if (a > b)
            {
                return a + 1;
            }
            else
            {
                return b + 1;
            }
        }
        return 0;
    }
    fun palindromicPath(root: TreeNode ? ): Unit
    {
        var size: Int = this.height(root);
        if (size == 0)
        {
            return;
        }
        // auxiliary space which is used to collect path
        var auxiliary: Array < Int > = Array(size)
        {
            0
        };
        this.findPath(root, auxiliary, 0);
    }
}
fun main(args: Array < String > ): Unit
{
    var tree: BinaryTree = BinaryTree();
    /*      4
           / \
          5   7
         / \   \
        5   3   7
       /   / \   \
      4   4   5   4
             / \
            1   4
    -----------------------
        Binary Tree

    */
    tree.root = TreeNode(4);
    tree.root?.left = TreeNode(5);
    tree.root?.right = TreeNode(7);
    tree.root?.left?.left = TreeNode(5);
    tree.root?.left?.left?.left = TreeNode(4);
    tree.root?.left?.right = TreeNode(3);
    tree.root?.left?.right?.left = TreeNode(4);
    tree.root?.left?.right?.right = TreeNode(5);
    tree.root?.left?.right?.right?.left = TreeNode(5);
    tree.root?.left?.right?.right?.right = TreeNode(4);
    tree.root?.right?.right = TreeNode(7);
    tree.root?.right?.right?.right = TreeNode(4);
    tree.palindromicPath(tree.root);
}

Output

 4 5 5 4
 4 5 3 5 4
 4 7 7 4

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post