Find mirror of a given node in binary tree

Here given code implementation process.
/*
C Program
Find mirror of a given node in 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 *newTree()
{
// 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 *newNode(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;
}
// Find mirror of given node
struct TreeNode *isMirror(struct TreeNode *node, struct TreeNode *left, struct TreeNode *right)
{
if (left == NULL || right == NULL)
{
// When any subtree are missing
return NULL;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
struct TreeNode *result = isMirror(node, left->left, right->right);
if (result == NULL)
{
result = isMirror(node, left->right, right->left);
}
return result;
}
// Handles the request to find mirror of given node
void findMirrorNode(struct TreeNode *root, struct TreeNode *node)
{
if (root == NULL || node == NULL)
{
return;
}
struct TreeNode *result = isMirror(node, root->left, root->right);
printf(" Mirror of node %d is : ", node->data);
if (result == NULL)
{
// When mirror node not found
printf(" None\n");
}
else
{
printf(" %d \n", result->data);
}
}
int main()
{
// Define tree
struct BinaryTree *tree = newTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree->root = newNode(-1);
tree->root->left = newNode(2);
tree->root->right = newNode(8);
tree->root->left->left = newNode(3);
tree->root->left->right = newNode(-3);
tree->root->left->right->left = newNode(-7);
tree->root->left->right->left->left = newNode(9);
tree->root->right->left = newNode(6);
tree->root->right->right = newNode(5);
tree->root->right->left->right = newNode(4);
tree->root->right->right->right = newNode(-6);
tree->root->right->left->right->left = newNode(1);
tree->root->right->left->right->right = newNode(-2);
tree->root->right->left->right->left->left = newNode(7);
struct TreeNode *node = tree->root->right->left->right->right;
findMirrorNode(tree->root, node);
node = tree->root->left->left;
findMirrorNode(tree->root, node);
node = tree->root->right->right->right;
findMirrorNode(tree->root, node);
return 0;
}
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
/*
Java Program
Find mirror of a given node in 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;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
// Find mirror of given node
public TreeNode isMirror(TreeNode node, TreeNode left, TreeNode right)
{
if (left == null || right == null)
{
// When any subtree are missing
return null;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
TreeNode result = isMirror(node, left.left, right.right);
if (result == null)
{
result = isMirror(node, left.right, right.left);
}
return result;
}
// Handles the request to find mirror of given node
public void findMirrorNode(TreeNode node)
{
if (this.root == null || node == null)
{
return;
}
TreeNode result = isMirror(node, this.root.left, this.root.right);
System.out.print(" Mirror of node " + node.data + " is : ");
if (result == null)
{
// When mirror node not found
System.out.print(" None\n");
}
else
{
System.out.print(" " + result.data + " \n");
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(-1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(-3);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(-6);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.left.left = new TreeNode(7);
TreeNode node = tree.root.right.left.right.right;
tree.findMirrorNode(node);
node = tree.root.left.left;
tree.findMirrorNode(node);
node = tree.root.right.right.right;
tree.findMirrorNode(node);
}
}
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Find mirror of a given node in 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;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
// Find mirror of given node
TreeNode *isMirror(TreeNode *node, TreeNode *left, TreeNode *right)
{
if (left == NULL || right == NULL)
{
// When any subtree are missing
return NULL;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
TreeNode *result = this->isMirror(node, left->left, right->right);
if (result == NULL)
{
result = this->isMirror(node, left->right, right->left);
}
return result;
}
// Handles the request to find mirror of given node
void findMirrorNode(TreeNode *node)
{
if (this->root == NULL || node == NULL)
{
return;
}
TreeNode *result = this->isMirror(node, this->root->left, this->root->right);
cout << " Mirror of node " << node->data << " is : ";
if (result == NULL)
{
// When mirror node not found
cout << " None\n";
}
else
{
cout << " " << result->data << " \n";
}
}
};
int main()
{
BinaryTree tree = BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(-1);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(8);
tree.root->left->left = new TreeNode(3);
tree.root->left->right = new TreeNode(-3);
tree.root->left->right->left = new TreeNode(-7);
tree.root->left->right->left->left = new TreeNode(9);
tree.root->right->left = new TreeNode(6);
tree.root->right->right = new TreeNode(5);
tree.root->right->left->right = new TreeNode(4);
tree.root->right->right->right = new TreeNode(-6);
tree.root->right->left->right->left = new TreeNode(1);
tree.root->right->left->right->right = new TreeNode(-2);
tree.root->right->left->right->left->left = new TreeNode(7);
TreeNode *node = tree.root->right->left->right->right;
tree.findMirrorNode(node);
node = tree.root->left->left;
tree.findMirrorNode(node);
node = tree.root->right->right->right;
tree.findMirrorNode(node);
return 0;
}
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
// Include namespace system
using System;
/*
C# Program
Find mirror of a given node in 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;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
// Find mirror of given node
public TreeNode isMirror(TreeNode node, TreeNode left, TreeNode right)
{
if (left == null || right == null)
{
// When any subtree are missing
return null;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
TreeNode result = isMirror(node, left.left, right.right);
if (result == null)
{
result = isMirror(node, left.right, right.left);
}
return result;
}
// Handles the request to find mirror of given node
public void findMirrorNode(TreeNode node)
{
if (this.root == null || node == null)
{
return;
}
TreeNode result = isMirror(node, this.root.left, this.root.right);
Console.Write(" Mirror of node " + node.data + " is : ");
if (result == null)
{
// When mirror node not found
Console.Write(" None\n");
}
else
{
Console.Write(" " + result.data + " \n");
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(-1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(-3);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(-6);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.left.left = new TreeNode(7);
TreeNode node = tree.root.right.left.right.right;
tree.findMirrorNode(node);
node = tree.root.left.left;
tree.findMirrorNode(node);
node = tree.root.right.right.right;
tree.findMirrorNode(node);
}
}
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
<?php
/*
Php Program
Find mirror of a given node in binary tree
*/
// Tree Node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
function __construct()
{
$this->root = null;
}
// Find mirror of given node
public function isMirror($node, $left, $right)
{
if ($left == null || $right == null)
{
// When any subtree are missing
return null;
}
if ($left == $node)
{
return $right;
}
if ($right == $node)
{
return $left;
}
$result = $this->isMirror($node, $left->left, $right->right);
if ($result == null)
{
$result = $this->isMirror($node, $left->right, $right->left);
}
return $result;
}
// Handles the request to find mirror of given node
public function findMirrorNode($node)
{
if ($this->root == null || $node == null)
{
return;
}
$result = $this->isMirror($node, $this->root->left, $this->root->right);
echo " Mirror of node ". $node->data ." is : ";
if ($result == null)
{
// When mirror node not found
echo " None\n";
}
else
{
echo " ". $result->data ." \n";
}
}
}
function main()
{
$tree = new BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
$tree->root = new TreeNode(-1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(8);
$tree->root->left->left = new TreeNode(3);
$tree->root->left->right = new TreeNode(-3);
$tree->root->left->right->left = new TreeNode(-7);
$tree->root->left->right->left->left = new TreeNode(9);
$tree->root->right->left = new TreeNode(6);
$tree->root->right->right = new TreeNode(5);
$tree->root->right->left->right = new TreeNode(4);
$tree->root->right->right->right = new TreeNode(-6);
$tree->root->right->left->right->left = new TreeNode(1);
$tree->root->right->left->right->right = new TreeNode(-2);
$tree->root->right->left->right->left->left = new TreeNode(7);
$node = $tree->root->right->left->right->right;
$tree->findMirrorNode($node);
$node = $tree->root->left->left;
$tree->findMirrorNode($node);
$node = $tree->root->right->right->right;
$tree->findMirrorNode($node);
}
main();
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
/*
Node Js Program
Find mirror of a given node in binary tree
*/
// Tree Node
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
// Find mirror of given node
isMirror(node, left, right)
{
if (left == null || right == null)
{
// When any subtree are missing
return null;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
var result = this.isMirror(node, left.left, right.right);
if (result == null)
{
result = this.isMirror(node, left.right, right.left);
}
return result;
}
// Handles the request to find mirror of given node
findMirrorNode(node)
{
if (this.root == null || node == null)
{
return;
}
var result = this.isMirror(node, this.root.left, this.root.right);
process.stdout.write(" Mirror of node " + node.data + " is : ");
if (result == null)
{
// When mirror node not found
process.stdout.write(" None\n");
}
else
{
process.stdout.write(" " + result.data + " \n");
}
}
}
function main()
{
var tree = new BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(-1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(-3);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(-6);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.left.left = new TreeNode(7);
var node = tree.root.right.left.right.right;
tree.findMirrorNode(node);
node = tree.root.left.left;
tree.findMirrorNode(node);
node = tree.root.right.right.right;
tree.findMirrorNode(node);
}
main();
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
# Python 3 Program
# Find mirror of a given node in binary tree
# Tree Node
class TreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
# Find mirror of given node
def isMirror(self, node, left, right) :
if (left == None or right == None) :
# When any subtree are missing
return None
if (left == node) :
return right
if (right == node) :
return left
result = self.isMirror(node, left.left, right.right)
if (result == None) :
result = self.isMirror(node, left.right, right.left)
return result
# Handles the request to find mirror of given node
def findMirrorNode(self, node) :
if (self.root == None or node == None) :
return
result = self.isMirror(node, self.root.left, self.root.right)
print(" Mirror of node ", node.data ," is : ", end = "")
if (result == None) :
# When mirror node not found
print(" None")
else :
print(" ", result.data ," ")
def main() :
tree = BinaryTree()
#
# -1
# / \
# 2 8
# / \ / \
# 3 -3 6 5
# / \ \
# -7 4 -6
# / / \
# 9 1 -2
# /
# 7
# -----------------------
# Binary Tree
# -----------------------
#
tree.root = TreeNode(-1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(8)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(-3)
tree.root.left.right.left = TreeNode(-7)
tree.root.left.right.left.left = TreeNode(9)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(5)
tree.root.right.left.right = TreeNode(4)
tree.root.right.right.right = TreeNode(-6)
tree.root.right.left.right.left = TreeNode(1)
tree.root.right.left.right.right = TreeNode(-2)
tree.root.right.left.right.left.left = TreeNode(7)
node = tree.root.right.left.right.right
tree.findMirrorNode(node)
node = tree.root.left.left
tree.findMirrorNode(node)
node = tree.root.right.right.right
tree.findMirrorNode(node)
if __name__ == "__main__": main()
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
# Ruby Program
# Find mirror of a given node in 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
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Find mirror of given node
def isMirror(node, left, right)
if (left == nil || right == nil)
# When any subtree are missing
return nil
end
if (left == node)
return right
end
if (right == node)
return left
end
result = self.isMirror(node, left.left, right.right)
if (result == nil)
result = self.isMirror(node, left.right, right.left)
end
return result
end
# Handles the request to find mirror of given node
def findMirrorNode(node)
if (self.root == nil || node == nil)
return
end
result = self.isMirror(node, self.root.left, self.root.right)
print(" Mirror of node ", node.data ," is : ")
if (result == nil)
# When mirror node not found
print(" None\n")
else
print(" ", result.data ," \n")
end
end
end
def main()
tree = BinaryTree.new()
#
# -1
# / \
# 2 8
# / \ / \
# 3 -3 6 5
# / \ \
# -7 4 -6
# / / \
# 9 1 -2
# /
# 7
# -----------------------
# Binary Tree
# -----------------------
#
tree.root = TreeNode.new(-1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(8)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(-3)
tree.root.left.right.left = TreeNode.new(-7)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.right.left = TreeNode.new(6)
tree.root.right.right = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(-6)
tree.root.right.left.right.left = TreeNode.new(1)
tree.root.right.left.right.right = TreeNode.new(-2)
tree.root.right.left.right.left.left = TreeNode.new(7)
node = tree.root.right.left.right.right
tree.findMirrorNode(node)
node = tree.root.left.left
tree.findMirrorNode(node)
node = tree.root.right.right.right
tree.findMirrorNode(node)
end
main()
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
/*
Scala Program
Find mirror of a given node in binary tree
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Find mirror of given node
def isMirror(node: TreeNode, left: TreeNode, right: TreeNode): TreeNode = {
if (left == null || right == null)
{
// When any subtree are missing
return null;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
var result: TreeNode = this.isMirror(node, left.left, right.right);
if (result == null)
{
result = this.isMirror(node, left.right, right.left);
}
return result;
}
// Handles the request to find mirror of given node
def findMirrorNode(node: TreeNode): Unit = {
if (this.root == null || node == null)
{
return;
}
var result: TreeNode = this.isMirror(node, this.root.left, this.root.right);
print(" Mirror of node " + node.data + " is : ");
if (result == null)
{
// When mirror node not found
print(" None\n");
}
else
{
print(" " + result.data + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(-1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(8);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(-3);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(-6);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.root.right.left.right.left.left = new TreeNode(7);
var node: TreeNode = tree.root.right.left.right.right;
tree.findMirrorNode(node);
node = tree.root.left.left;
tree.findMirrorNode(node);
node = tree.root.right.right.right;
tree.findMirrorNode(node);
}
}
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
/*
Swift 4 Program
Find mirror of a given node in 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;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Find mirror of given node
func isMirror(_ node: TreeNode? , _ left : TreeNode? , _ right : TreeNode? )->TreeNode?
{
if (left == nil || right == nil)
{
// When any subtree are missing
return nil;
}
if (left === node)
{
return right;
}
if (right === node)
{
return left;
}
var result: TreeNode? = self.isMirror(node, left!.left, right!.right);
if (result == nil)
{
result = self.isMirror(node, left!.right, right!.left);
}
return result;
}
// Handles the request to find mirror of given node
func findMirrorNode(_ node: TreeNode? )
{
if (self.root == nil || node == nil)
{
return;
}
let result: TreeNode? = self.isMirror(node, self.root!.left, self.root!.right);
print(" Mirror of node", node!.data ,"is : ", terminator: "");
if (result == nil)
{
// When mirror node not found
print(" None");
}
else
{
print(" ", result!.data ," ");
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(-1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(8);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(-3);
tree.root!.left!.right!.left = TreeNode(-7);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.right!.left = TreeNode(6);
tree.root!.right!.right = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(-6);
tree.root!.right!.left!.right!.left = TreeNode(1);
tree.root!.right!.left!.right!.right = TreeNode(-2);
tree.root!.right!.left!.right!.left!.left = TreeNode(7);
var node: TreeNode? = tree.root!.right!.left!.right!.right;
tree.findMirrorNode(node);
node = tree.root!.left!.left;
tree.findMirrorNode(node);
node = tree.root!.right!.right!.right;
tree.findMirrorNode(node);
}
main();
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
/*
Kotlin Program
Find mirror of a given node in 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;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Find mirror of given node
fun isMirror(node: TreeNode ? , left : TreeNode ? , right : TreeNode ? ): TreeNode ?
{
if (left == null || right == null)
{
// When any subtree are missing
return null;
}
if (left == node)
{
return right;
}
if (right == node)
{
return left;
}
var result: TreeNode ? = this.isMirror(node, left.left, right.right);
if (result == null)
{
result = this.isMirror(node, left.right, right.left);
}
return result;
}
// Handles the request to find mirror of given node
fun findMirrorNode(node: TreeNode ? ): Unit
{
if (this.root == null || node == null)
{
return;
}
var result: TreeNode ? = this.isMirror(node, this.root?.left, this.root?.right);
print(" Mirror of node " + node.data + " is : ");
if (result == null)
{
// When mirror node not found
print(" None\n");
}
else
{
print(" " + result.data + " \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var tree: BinaryTree = BinaryTree();
/*
-1
/ \
2 8
/ \ / \
3 -3 6 5
/ \ \
-7 4 -6
/ / \
9 1 -2
/
7
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(-1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(8);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(-3);
tree.root?.left?.right?.left = TreeNode(-7);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.right?.left = TreeNode(6);
tree.root?.right?.right = TreeNode(5);
tree.root?.right?.left?.right = TreeNode(4);
tree.root?.right?.right?.right = TreeNode(-6);
tree.root?.right?.left?.right?.left = TreeNode(1);
tree.root?.right?.left?.right?.right = TreeNode(-2);
tree.root?.right?.left?.right?.left?.left = TreeNode(7);
var node: TreeNode ? = tree.root?.right?.left?.right?.right;
tree.findMirrorNode(node);
node = tree.root?.left?.left;
tree.findMirrorNode(node);
node = tree.root?.right?.right?.right;
tree.findMirrorNode(node);
}
Output
Mirror of node -2 is : 9
Mirror of node 3 is : 5
Mirror of node -6 is : None
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