Given two binary tree with same structure but may have different arrangement of value and given an integer K. The task is to check that after exactly K swap on first tree, will it become mirror of second one. In one swap we take two node of same parent and swap its left and right subtree.
Examples:
Input: K = 1
1 1
/ \ / \
2 3 2 3
Output: YesInput: K = 4
11 11
/ \ / \
25 15 25 15
/ \ / \ / \ / \
7 9 10 21 10 21 9 7
Output: Yes
Explanation: Here first we need to swap two pairs (25, 15) and (10 ,21) in the first tree hence K = 2. And then we do swap of (21, 7) and (10, 9) therefore here is total of 4 swap.
Approach: The basic approach to solve this problem is to use recursion and stack based on below idea:
The idea is to traverse the first tree and check by swapping nodes recursively, if the tree becomes mirror image of second tree.
Follow the steps below to implement the above approach:
- Check all the respective nodes of both the trees one by one with the help of iterative inorder traversal.
- If found that the respective data parts of both the trees are not matching, then we simply increment the count of swaps needed
- Once the traversal is complete, check for below condition and return Yes if any of below condition is true:
- if our count is same as K, or
- if count is less than K and (K – count) is even,
- Else return No.
Below is the implementation of the above approach:
C++
// C++ program of above approach #include <bits/stdc++.h> using namespace std; // A binary tree node has data, // pointer to left child // and a pointer to right child class node { public : int data; node* left; node* right; }; // Create new node. node* newNode( int data) { node* Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL; return (Node); } // Function to convert tree // into its mirror tree void convert(node* root) { if (!root) return ; // Recursively call left // and right node convert(root->left); convert(root->right); // Swap left and right of any node swap(root->left, root->right); } // Function to check identical and // count no of swap needed to be int checkIdentical(node* p, node* q) { stack<node*> st1, st2; int count = 0; while (p || !st1.empty() && q || !st2.empty()) { // If p q are not // null push in stack if (p && q) { st1.push(p); st2.push(q); // Send p and q // to its left child p = p->left; q = q->left; } // If p and q are null // pop node from stack else { p = st1.top(); q = st2.top(); st1.pop(); st2.pop(); // If data not match // increment count if (p->data != q->data) count++; // Send p and q to // its right child p = p->right; q = q->right; } } // Return count/2 because // we swap pairs return count / 2; } /* Driver code*/ int main() { node* root1 = newNode(11); root1->left = newNode(25); root1->right = newNode(15); root1->left->left = newNode(7); root1->left->right = newNode(9); root1->right->left = newNode(10); root1->right->right = newNode(21); node* root2 = newNode(11); root2->left = newNode(25); root2->right = newNode(15); root2->left->left = newNode(10); root2->left->right = newNode(21); root2->right->left = newNode(9); root2->right->right = newNode(7); int K = 4; // First convert first // tree into mirror tree convert(root1); int count = checkIdentical(root1, root2); if (count <= K && (K - count) % 2 == 0) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { // A binary tree node has data, // pointer to left child // and a pointer to right child public static class node { int data; node left; node right; } // Create new node. public static node newNode( int data) { node Node = new node(); Node.data = data; Node.left = null ; Node.right = null ; return (Node); } // Swapping the node static void swap(node m, node n) { // Swapping the values node temp = m; m = n; n = temp; } // Function to convert tree // into its mirror tree public static void convert(node root) { if (root== null ) return ; // Recursively call left // and right node convert(root.left); convert(root.right); // Swap left and right of any node swap(root.left, root.right); } // Function to check identical and // count no of swap needed to be public static int checkIdentical(node p, node q) { Stack<node> st1= new Stack<>(); Stack<node> st2= new Stack<>(); int count = 0 ; while (p!= null || !st1.empty() && q!= null || !st2.empty()) { // If p q are not // null push in stack if (p!= null && q!= null ) { st1.push(p); st2.push(q); // Send p and q // to its left child p = p.left; q = q.left; } // If p and q are null // pop node from stack else { p = st1.peek(); q = st2.peek(); st1.pop(); st2.pop(); // If data not match // increment count if (p.data != q.data) count++; // Send p and q to // its right child p = p.right; q = q.right; } } // Return count/2 because // we swap pairs return count / 2 ; } // Driver Code public static void main(String[] args) { node root1 = newNode( 11 ); root1.left = newNode( 25 ); root1.right = newNode( 15 ); root1.left.left = newNode( 7 ); root1.left.right = newNode( 9 ); root1.right.left = newNode( 10 ); root1.right.right = newNode( 21 ); node root2 = newNode( 11 ); root2.left = newNode( 25 ); root2.right = newNode( 15 ); root2.left.left = newNode( 10 ); root2.left.right = newNode( 21 ); root2.right.left = newNode( 9 ); root2.right.right = newNode( 7 ); int K = 4 ; // First convert first // tree into mirror tree convert(root1); int count = checkIdentical(root1, root2); if (count <= K && (K - count) % 2 == 0 ) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by jana_sayantan. |
Python3
# Python code for the above approach # Node Class class Node: def __init__( self , d): self .data = d self .left = None self .right = None class LinkedList: def __init__( self ): self .head = None ## Function to convert tree ## into its mirror tree def convert(head): if (head = = None ): return ## Recursively call left ## and right node convert(head.left) convert(head.right) ## Swap left and right of any node head.left, head.right = head.right, head.left ## Function to check identical and ## count no of swap needed to be def checkIdentical(head1, head2): st1 = [] st2 = [] count = 0 while ( (head1! = None ) or ( len (st1)! = 0 )) and ( (head2! = None ) or ( len (st2)! = 0 )): ## If head1 head2 are not ## none push in stack if ((head1! = None ) and (head2! = None )): st1.append(head1) st2.append(head2) ## Send head1 and head2 ## to its left child head1 = head1.left head2 = head2.left ## If head1 and head2 are null ## pop node from stack else : head1 = st1[ - 1 ] head2 = st2[ - 1 ] st1.pop() st2.pop() ## If data not match ## increment count if (head1.data ! = head2.data): count + = 1 ## Send head1 and head2 to ## its right child head1 = head1.right head2 = head2.right ## Return count/2 because ## we swap pairs return count / 2 # Driver Code if __name__ = = '__main__' : llist1 = LinkedList() llist1.head = Node( 11 ) llist1.head.left = Node( 25 ) llist1.head.right = Node( 15 ) llist1.head.left.left = Node( 7 ) llist1.head.left.right = Node( 9 ) llist1.head.right.left = Node( 10 ) llist1.head.right.right = Node( 21 ) llist2 = LinkedList() llist2.head = Node( 11 ) llist2.head.left = Node( 25 ) llist2.head.right = Node( 15 ) llist2.head.left.left = Node( 10 ) llist2.head.left.right = Node( 21 ) llist2.head.right.left = Node( 9 ) llist2.head.right.right = Node( 7 ) K = 4 ## First convert first ## tree into mirror tree convert(llist1.head) count = checkIdentical(llist1.head, llist2.head) if (count < = K and (K - count) % 2 = = 0 ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by subhamgoyal2014. |
C#
// C# code for the above approach: using System; using System.Collections.Generic; public class GFG { // A binary tree node has data, // pointer to left child // and a pointer to right child public class node { public int data; public node left; public node right; } // Create new node. public static node newNode( int data) { node Node = new node(); Node.data = data; Node.left = null ; Node.right = null ; return (Node); } // Swapping the node static void swap(node m, node n) { // Swapping the values node temp = m; m = n; n = temp; } // Function to convert tree // into its mirror tree public static void convert(node root) { if (root== null ) return ; // Recursively call left // and right node convert(root.left); convert(root.right); // Swap left and right of any node swap(root.left, root.right); } // Function to check identical and // count no of swap needed to be public static int checkIdentical(node p, node q) { Stack<node> st1= new Stack<node>(); Stack<node> st2= new Stack<node>(); int count = 0; while (p!= null || st1.Count!=0 && q!= null || st2.Count!=0) { // If p q are not // null push in stack if (p!= null && q!= null ) { st1.Push(p); st2.Push(q); // Send p and q // to its left child p = p.left; q = q.left; } // If p and q are null // pop node from stack else { p = st1.Peek(); q = st2.Peek(); st1.Pop(); st2.Pop(); // If data not match // increment count if (p.data != q.data) count++; // Send p and q to // its right child p = p.right; q = q.right; } } // Return count/2 because // we swap pairs return count / 2; } // Driver Code public static void Main(String[] args) { node root1 = newNode(11); root1.left = newNode(25); root1.right = newNode(15); root1.left.left = newNode(7); root1.left.right = newNode(9); root1.right.left = newNode(10); root1.right.right = newNode(21); node root2 = newNode(11); root2.left = newNode(25); root2.right = newNode(15); root2.left.left = newNode(10); root2.left.right = newNode(21); root2.right.left = newNode(9); root2.right.right = newNode(7); int K = 4; // First convert first // tree into mirror tree convert(root1); int count = checkIdentical(root1, root2); if (count <= K && (K - count) % 2 == 0) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code contributed by shikhasingrajput |
Javascript
// Javascript program for the above approach // A binary tree node has data, // pointer to left child // and a pointer to right child class node { // Creates new node constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Swapping the node function swap(m, n) { // Swapping the values let temp = m; m = n; n = temp; } // Function to convert tree // into its mirror tree function convert(root) { if (root == null ) { return ; } // Recursively call left and right node convert(root.left); convert(root.right); // Swap left and right of any node swap(root.left, root.right); } // Function to check identical and // count no of swap needed to be function checkIdentical(p, q) { let st1 = []; let st2 = []; let count = 0; while (p || st1.length || q || st2.length) { // If p q are not // null push in stack if (p && q) { st1.push(p); st2.push(q); // Send p and q // to its left child p = p.left; q = q.left; } else { p = st1[st1.length - 1]; q = st2[st2.length - 1]; st1.pop(); st2.pop(); // If data not match // increment count if (p.data != q.data) count++; // Send p and q to // its right child p = p.right; q = q.right; } } // Return count/2 because // we swap pairs return count / 2; } // Driver code let root1 = new node(11); root1.left = new node(25); root1.right = new node(15); root1.left.left = new node(7); root1.left.right = new node(9); root1.right.left = new node(10); root1.right.right = new node(21); let root2 = new node(11); root2.left = new node(25); root2.right = new node(15); root2.left.left = new node(10); root2.left.right = new node(21); root2.right.left = new node(9); root2.right.right = new node(7); let k = 4; // First convert first // tree into mirror tree convert(root1); let count = checkIdentical(root1,root2); if (count <= k && ((k - count) % 2) == 0){ console.log( "Yes" ); } else { console.log( "No" ); } // This code is contributed by Ishan Khandelwal |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!