Skip to main content

Isomorphic Tree in Binary Tree

 Check if Tree is Isomorphic


Given two Binary Trees. Check whether they are Isomorphic or not.

Note: 
Two trees are called isomorphic if one can be obtained from another by a series of flips, i.e. by swapping left and right children of several nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.
For example, the following two trees are isomorphic with the following sub-trees flipped: 2 and 3, NULL and 6, 7 and 8.
ISomorphicTrees

Example 1:

Input:
 T1    1     T2:   1
     /   \        /  \
    2     3      3    2
   /            /
  4            4
Output: No

Example 2:

Input:
T1    1     T2:    1
    /  \         /   \
   2    3       3     2
  /                    \
  4                     4
Output: Yes

Your Task:
You don't need to read input or print anything. Your task is to complete the function isomorphic() that takes the root nodes of both the Binary Trees as its input and returns True if the two trees are isomorphic. Else, it returns False. (The driver code will print Yes if the returned values are true, otherwise false.)

Expected Time Complexity: O(min(M, N)) where M and N are the sizes of the two trees.
Expected Auxiliary Space: O(min(H1, H2)) where H1 and H2 are the heights of the two trees.

Constraints:
1<=Number of nodes<=105


solution : 


class Solution{
  public:
    // Return True if the given trees are isomotphic. Else return False.
    bool isIsomorphic(Node *root1,Node *root2)
    {
        //add code here.
        if(!root1 && !root2)
        return true;
        if(!root1 || !root2)
        return false;
        if(root1 ->data != root2 ->data)
        return false;
        bool a = isIsomorphic(root1->left ,root2->left) && isIsomorphic(root1->right , root2->right);
        bool b = isIsomorphic(root1->left ,root2->right) && isIsomorphic(root1->right , root2->left);
        return a | b;
     
     
   
    }
};



Comments

Popular posts from this blog

[PDF DOWNLOAD] AKTU Quantum series data structure b.tech 2nd year download

  All AKTU Quantums are available here. Get your hands on AKTU Quantums and boost your grades in AKTU semester exams. You can either search them category wise or can use the search bar or can manually search on this page. Download aktu second year quantum pdf data structures  download  data structures quantum aktu download aktu data structures quantum click here to download  write in comment section if you want quantum of any other subject.

Root to Leaf Paths | binary tree | geeksforgeeks solution

  Root to Leaf Paths Given a Binary Tree of size N, you need to find all the possible paths from root node to all the leaf node's of the binary tree. Example 1: Input: 1 / \ 2 3 Output: 1 2 #1 3 # Explanation: All possible paths: 1->2 1->3 Example 2: Input:   10   / \   20 30   / \   40 60 Output: 10 20 40 #10 20 60 #10 30 # Your Task: Your task is to complete the function  Paths()  that takes the root node as an argument and return all the possible path. (All the path are printed '#' separated by the driver's code.) Note:  The return type cpp:  vector java:  ArrayList> python:  list of list Expected Time Complexity:  O(N). Expected Auxiliary Space:  O(H). Note:  H is the height of the tree. Constraints: 1<=N<=10 3 Note:  The  Input/Ouput  format and  Example  given, are used for the system'...

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...