Find mirror of a given node in Binary tree
Given a Binary tree, the problem is to find the mirror of a given node. The mirror of a node is a node which exists at the mirror position of the node in opposite subtree at the root.
Examples:
In above tree- Node 2 and 3 are mirror nodes Node 4 and 6 are mirror nodes.
We can have a recursive solution for finding mirror nodes. The algorithm is following –
1) Start from the root of the tree and recur nodes from both subtree simultaneously using two pointers for left and right nodes. 2) First recur all the external nodes and store returned value in mirror variable. 3) If current node value is equal to target node, return the value of opposite pointer else repeat step 2. 4) If no external node is left and mirror is none, recur internal nodes.
Implementation:
C++
// C++ program to find the mirror Node // in Binary tree #include <bits/stdc++.h> using namespace std; /* A binary tree Node has data, pointer to left child and a pointer to right child */ struct Node { int key; struct Node* left, *right; }; // create new Node and initialize it struct Node* newNode( int key) { struct Node* n = ( struct Node*) malloc ( sizeof ( struct Node*)); if (n != NULL) { n->key = key; n->left = NULL; n->right = NULL; return n; } else { cout << "Memory allocation failed!" << endl; exit (1); } } // recursive function to find mirror of Node int findMirrorRec( int target, struct Node* left, struct Node* right) { /* if any of the Node is none then Node itself and descendant have no mirror, so return none, no need to further explore! */ if (left == NULL || right == NULL) return 0; /* if left Node is target Node, then return right's key (that is mirror) and vice versa */ if (left->key == target) return right->key; if (right->key == target) return left->key; // first recur external Nodes int mirror_val = findMirrorRec(target, left->left, right->right); if (mirror_val) return mirror_val; // if no mirror found, recur internal Nodes findMirrorRec(target, left->right, right->left); } // interface for mirror search int findMirror( struct Node* root, int target) { if (root == NULL) return 0; if (root->key == target) return target; return findMirrorRec(target, root->left, root->right); } // Driver Code int main() { struct Node* root = newNode(1); root-> left = newNode(2); root->left->left = newNode(4); root->left->left->right = newNode(7); root->right = newNode(3); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->left = newNode(8); root->right->left->right = newNode(9); // target Node whose mirror have to be searched int target = root->left->left->key; int mirror = findMirror(root, target); if (mirror) cout << "Mirror of Node " << target << " is Node " << mirror << endl; else cout << "Mirror of Node " << target << " is NULL! " << endl; } // This code is contributed by SHUBHAMSINGH10 |
C
// C program to find the mirror Node in Binary tree #include <stdio.h> #include <stdlib.h> /* A binary tree Node has data, pointer to left child and a pointer to right child */ struct Node { int key; struct Node* left, *right; }; // create new Node and initialize it struct Node* newNode( int key) { struct Node* n = ( struct Node*) malloc ( sizeof ( struct Node*)); if (n != NULL) { n->key = key; n->left = NULL; n->right = NULL; return n; } else { printf ( "Memory allocation failed!" ); exit (1); } } // recursive function to find mirror of Node int findMirrorRec( int target, struct Node* left, struct Node* right) { /* if any of the Node is none then Node itself and descendant have no mirror, so return none, no need to further explore! */ if (left==NULL || right==NULL) return 0; /* if left Node is target Node, then return right's key (that is mirror) and vice versa */ if (left->key == target) return right->key; if (right->key == target) return left->key; // first recur external Nodes int mirror_val = findMirrorRec(target, left->left, right->right); if (mirror_val) return mirror_val; // if no mirror found, recur internal Nodes findMirrorRec(target, left->right, right->left); } // interface for mirror search int findMirror( struct Node* root, int target) { if (root == NULL) return 0; if (root->key == target) return target; return findMirrorRec(target, root->left, root->right); } // Driver int main() { struct Node* root = newNode(1); root-> left = newNode(2); root->left->left = newNode(4); root->left->left->right = newNode(7); root->right = newNode(3); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->left = newNode(8); root->right->left->right = newNode(9); // target Node whose mirror have to be searched int target = root->left->left->key; int mirror = findMirror(root, target); if (mirror) printf ( "Mirror of Node %d is Node %d\n" , target, mirror); else printf ( "Mirror of Node %d is NULL!\n" , target); } |
Java
// Java program to find the mirror Node in Binary tree class GfG { /* A binary tree Node has data, pointer to left child and a pointer to right child */ static class Node { int key; Node left, right; } // create new Node and initialize it static Node newNode( int key) { Node n = new Node(); n.key = key; n.left = null ; n.right = null ; return n; } // recursive function to find mirror of Node static int findMirrorRec( int target, Node left, Node right) { /* if any of the Node is none then Node itself and descendant have no mirror, so return none, no need to further explore! */ if (left== null || right== null ) return 0 ; /* if left Node is target Node, then return right's key (that is mirror) and vice versa */ if (left.key == target) return right.key; if (right.key == target) return left.key; // first recur external Nodes int mirror_val = findMirrorRec(target, left.left, right.right); if (mirror_val != 0 ) return mirror_val; // if no mirror found, recur internal Nodes return findMirrorRec(target, left.right, right.left); } // interface for mirror search static int findMirror(Node root, int target) { if (root == null ) return 0 ; if (root.key == target) return target; return findMirrorRec(target, root.left, root.right); } // Driver public static void main(String[] args) { Node root = newNode( 1 ); root.left = newNode( 2 ); root.left.left = newNode( 4 ); root.left.left.right = newNode( 7 ); root.right = newNode( 3 ); root.right.left = newNode( 5 ); root.right.right = newNode( 6 ); root.right.left.left = newNode( 8 ); root.right.left.right = newNode( 9 ); // target Node whose mirror have to be searched int target = root.left.left.key; int mirror = findMirror(root, target); if (mirror != 0 ) System.out.println( "Mirror of Node " + target + " is Node " + mirror); else System.out.println( "Mirror of Node " + target + " is null " ); } } |
Python3
# Python3 program to find the mirror node in # Binary tree class Node: '''A binary tree node has data, reference to left child and a reference to right child ''' def __init__( self , key, lchild = None , rchild = None ): self .key = key self .lchild = None self .rchild = None # recursive function to find mirror def findMirrorRec(target, left, right): # If any of the node is none then node itself # and descendant have no mirror, so return # none, no need to further explore! if left = = None or right = = None : return None # if left node is target node, then return # right's key (that is mirror) and vice versa if left.key = = target: return right.key if right.key = = target: return left.key # first recur external nodes mirror_val = findMirrorRec(target, left.lchild, right.rchild) if mirror_val ! = None : return mirror_val # if no mirror found, recur internal nodes findMirrorRec(target, left.rchild, right.lchild) # interface for mirror search def findMirror(root, target): if root = = None : return None if root.key = = target: return target return findMirrorRec(target, root.lchild, root.rchild) # Driver def main(): root = Node( 1 ) n1 = Node( 2 ) n2 = Node( 3 ) root.lchild = n1 root.rchild = n2 n3 = Node( 4 ) n4 = Node( 5 ) n5 = Node( 6 ) n1.lchild = n3 n2.lchild = n4 n2.rchild = n5 n6 = Node( 7 ) n7 = Node( 8 ) n8 = Node( 9 ) n3.rchild = n6 n4.lchild = n7 n4.rchild = n8 # target node whose mirror have to be searched target = n3.key mirror = findMirror(root, target) print ( "Mirror of node {} is node {}" . format (target, mirror)) if __name__ = = '__main__' : main() |
C#
// C# program to find the // mirror Node in Binary tree using System; class GfG { /* A binary tree Node has data, pointer to left child and a pointer to right child */ class Node { public int key; public Node left, right; } // create new Node and initialize it static Node newNode( int key) { Node n = new Node(); n.key = key; n.left = null ; n.right = null ; return n; } // recursive function to find mirror of Node static int findMirrorRec( int target, Node left, Node right) { /* if any of the Node is none then Node itself and descendant have no mirror, so return none, no need to further explore! */ if (left== null || right== null ) return 0; /* if left Node is target Node, then return right's key (that is mirror) and vice versa */ if (left.key == target) return right.key; if (right.key == target) return left.key; // first recur external Nodes int mirror_val = findMirrorRec(target, left.left, right.right); if (mirror_val != 0) return mirror_val; // if no mirror found, recur internal Nodes return findMirrorRec(target, left.right, right.left); } // interface for mirror search static int findMirror(Node root, int target) { if (root == null ) return 0; if (root.key == target) return target; return findMirrorRec(target, root.left, root.right); } // Driver code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.left.right = newNode(7); root.right = newNode(3); root.right.left = newNode(5); root.right.right = newNode(6); root.right.left.left = newNode(8); root.right.left.right = newNode(9); // target Node whose mirror have to be searched int target = root.left.left.key; int mirror = findMirror(root, target); if (mirror != 0) Console.WriteLine( "Mirror of Node " + target + " is Node " + mirror); else Console.WriteLine( "Mirror of Node " + target + " is null " ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find the mirror // Node in Binary tree /* A binary tree Node has data, pointer to left child and a pointer to right child */ class Node { // Create new Node and initialize it constructor(key) { this .key = key; this .left = this .right = null ; } } // Recursive function to find mirror of Node function findMirrorRec(target, left, right) { /* If any of the Node is none then Node itself and descendant have no mirror, so return none, no need to further explore! */ if (left == null || right == null ) return 0; /* If left Node is target Node, then return right's key (that is mirror) and vice versa */ if (left.key == target) return right.key; if (right.key == target) return left.key; // First recur external Nodes let mirror_val = findMirrorRec( target, left.left, right.right); if (mirror_val != 0) return mirror_val; // If no mirror found, recur internal Nodes return findMirrorRec(target, left.right, right.left); } // Interface for mirror search function findMirror(root, target) { if (root == null ) return 0; if (root.key == target) return target; return findMirrorRec(target, root.left, root.right); } // Driver code let root = new Node(1); root.left = new Node(2); root.left.left = new Node(4); root.left.left.right = new Node(7); root.right = new Node(3); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(8); root.right.left.right = new Node(9); // Target Node whose mirror have to be searched let target = root.left.left.key; let mirror = findMirror(root, target); if (mirror != 0) document.write( "Mirror of Node " + target + " is Node " + mirror + "<br>" ); else document.write( "Mirror of Node " + target + " is null " + "<br>" ); // This code is contributed by rag2127 </script> |
Output
Mirror of Node 4 is Node 6
Time Complexity:
Space Complexity :-The space complexity is O(H), where H is the height of the tree, due to the recursive call stack.
Another Approach:-
- So, the thought process behind this problem is that as we know that the mirror image will be in the same of the node.
- So, it is clear that we have to look into the same level.
- But also we have to find the position of the image which is mirror of the given node because all node in a level can not be the mirror node of a given node.
- So to do so we have to first find out the level as well as the position of the given node, So that we can find the mirror image.
- In initial moment we will take the position of the given node and level of the node as -1
- After this we will start traversing the tree using DFS algorithm and increase the level in each call as we are going down and set the position according to the call like if we are going left then we will decrease the position else we will increase the position by 1.
- As soon as we got the node with given target value we will set the position and level of the target node which was previously -1 to the current position and level.
- After this we have to check if we got the level and position of the target node and we are at the same level then we have to find out the mirror position and that we can identify by doing abs of the current position and target position because the position of any one or both can be negative.
- If we found the same abs(position) at same level then this is the mirror node, store this in your answer.
- Below is the implementation of this approach:-
Implementation:-
C++
// C++ program to find the mirror Node // in Binary tree #include <bits/stdc++.h> using namespace std; /* A binary tree Node has data, pointer to left child and a pointer to right child */ struct Node { int key; struct Node* left, *right; }; // create new Node and initialize it struct Node* newNode( int key) { struct Node* n = ( struct Node*) malloc ( sizeof ( struct Node*)); if (n != NULL) { n->key = key; n->left = NULL; n->right = NULL; return n; } else { cout << "Memory allocation failed!" << endl; exit (1); } } void findMirror(Node* root, int target, int &target_level, int &target_position, int level, int position, int &mirror) { if (!root) return ; //if node is target node if (root->key==target){ target_level=level; target_position = position; return ; } //checking if target has found then check for mirro if (target_level!=-1 and level==target_level and ( abs (position)== abs (target_position))){ mirror=root->key; return ; } //going left side of the node findMirror(root->left,target,target_level,target_position,level+1,position-1,mirror); //going right side of the node findMirror(root->right,target,target_level,target_position,level+1,position+1,mirror); } // Driver Code int main() { struct Node* root = newNode(1); root-> left = newNode(2); root->left->left = newNode(4); root->left->left->right = newNode(7); root->right = newNode(3); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->left = newNode(8); root->right->left->right = newNode(9); // target Node whose mirror have to be searched int target = root->left->left->key; int mirror = 0; int target_level=-1,target_position=-1; findMirror(root, target,target_level,target_position,0,0,mirror); if (mirror!=0) cout << "Mirror of Node " << target << " is Node " << mirror << endl; else cout << "Mirror of Node " << target << " is NULL! " << endl; } // This code is contributed by shubhamrajput6156 |
Java
import java.util.*; public class Gfg { /* A binary tree Node has data, pointer to left child and a pointer to right child */ static class Node { int key; Node left, right; }; // create new Node and initialize it static Node newNode( int key) { Node n = new Node(); n.key = key; n.left = null ; n.right = null ; return n; } static void findMirror(Node root, int target, int [] targetLevel, int [] targetPosition, int level, int position, int [] mirror) { if (root == null ) return ; // if node is target node if (root.key == target) { targetLevel[ 0 ] = level; targetPosition[ 0 ] = position; return ; } // checking if target has found then check for mirror if (targetLevel[ 0 ] != - 1 && level == targetLevel[ 0 ] && Math.abs(position) == Math.abs(targetPosition[ 0 ])) { mirror[ 0 ] = root.key; return ; } // going left side of the node findMirror(root.left, target, targetLevel, targetPosition, level + 1 , position - 1 , mirror); // going right side of the node findMirror(root.right, target, targetLevel, targetPosition, level + 1 , position + 1 , mirror); } // Driver Code public static void main(String[] args) { Node root = newNode( 1 ); root.left = newNode( 2 ); root.left.left = newNode( 4 ); root.left.left.right = newNode( 7 ); root.right = newNode( 3 ); root.right.left = newNode( 5 ); root.right.right = newNode( 6 ); root.right.left.left = newNode( 8 ); root.right.left.right = newNode( 9 ); // target Node whose mirror have to be searched int target = root.left.left.key; int [] mirror = new int [ 1 ]; int [] targetLevel = {- 1 }; int [] targetPosition = { 0 }; findMirror(root, target, targetLevel, targetPosition, 0 , 0 , mirror); if (mirror[ 0 ] != 0 ) { System.out.println( "Mirror of Node " + target + " is Node " + mirror[ 0 ]); } else { System.out.println( "Mirror of Node " + target + " is NULL!" ); } } } |
Python3
# Python program to find the mirror Node # in Binary tree # A binary tree Node has data, # pointer to left child and # a pointer to right child class Node: def __init__( self , key): self .key = key self .left = None self .right = None target_level = - 1 target_position = - 1 mirror = 0 def findMirror(root, target, level, position): global target_level, target_position, mirror if not root: return # If node is target node if root.key = = target: target_level = level target_position = position return # Checking if target has found then check for mirror if target_level ! = - 1 and level = = target_level and abs (position) = = abs (target_position): mirror = root.key return # Going left side of the node findMirror(root.left, target, level + 1 , position - 1 ) # Going right side of the node findMirror(root.right, target, level + 1 , position + 1 ) # Driver Code root = Node( 1 ) root.left = Node( 2 ) root.left.left = Node( 4 ) root.left.left.right = Node( 7 ) root.right = Node( 3 ) root.right.left = Node( 5 ) root.right.right = Node( 6 ) root.right.left.left = Node( 8 ) root.right.left.right = Node( 9 ) # Target Node whose mirror have to be searched target = root.left.left.key findMirror(root, target, 0 , 0 ) if mirror ! = 0 : print (f "Mirror of Node {target} is Node {mirror}" ) else : print (f "Mirror of Node {target} is NULL!" ) |
Javascript
// JavaScript program to find the mirror Node // in Binary tree /* A binary tree Node has data, pointer to left child and a pointer to right child */ class Node { constructor(key) { this .key = key; this .left = null ; this .right = null ; } } let target_level = -1; let target_position = -1; let mirror = 0; function findMirror(root, target, level, position) { if (!root) return ; // If node is target node if (root.key == target) { target_level = level; target_position = position; return ; } // Checking if target has found then check for mirror if (target_level != -1 && level == target_level && (Math.abs(position) == Math.abs(target_position))) { mirror = root.key; return ; } // Going left side of the node findMirror(root.left, target, level + 1, position - 1); // Going right side of the node findMirror(root.right, target, level + 1, position + 1); } // Driver Code let root = new Node(1); root.left = new Node(2); root.left.left = new Node(4); root.left.left.right = new Node(7); root.right = new Node(3); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(8); root.right.left.right = new Node(9); // Target Node whose mirror have to be searched let target = root.left.left.key; findMirror(root, target, 0, 0); if (mirror != 0) { console.log(`Mirror of Node ${target} is Node ${mirror}`); } else { console.log(`Mirror of Node ${target} is NULL!`); } |
C#
using System; public class Node { public int key; public Node left, right; } public class BinaryTree { public Node newNode( int key) { Node n = new Node(); n.key = key; n.left = null ; n.right = null ; return n; } public void findMirror(Node root, int target, ref int target_level, ref int target_position, int level, int position, ref int mirror) { if (root == null ) return ; // if node is target node if (root.key == target) { target_level = level; target_position = position; return ; } // checking if target has found then check for mirror if (target_level != -1 && level == target_level && (Math.Abs(position) == Math.Abs(target_position))) { mirror = root.key; return ; } // going left side of the node findMirror(root.left, target, ref target_level, ref target_position, level + 1, position - 1, ref mirror); // going right side of the node findMirror(root.right, target, ref target_level, ref target_position, level + 1, position + 1, ref mirror); } public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); Node root = tree.newNode(1); root.left = tree.newNode(2); root.left.left = tree.newNode(4); root.left.left.right = tree.newNode(7); root.right = tree.newNode(3); root.right.left = tree.newNode(5); root.right.right = tree.newNode(6); root.right.left.left = tree.newNode(8); root.right.left.right = tree.newNode(9); // target Node whose mirror have to be searched int target = root.left.left.key; int mirror = 0; int target_level = -1, target_position = -1; tree.findMirror(root, target, ref target_level, ref target_position, 0, 0, ref mirror); if (mirror != 0) Console.WriteLine( "Mirror of Node " + target + " is Node " + mirror); else Console.WriteLine( "Mirror of Node " + target + " is NULL!" ); } } |
Output
Mirror of Node 4 is Node 6
Time Complexity:- O(N) where N is number of nodes in the tree
Auxiliary Space:- O(H) Recursive stack, Where H is height of tree.
Contact Us