Skip to main content

Find mirror of a given node in binary tree

Find mirror of 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




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