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