Flip Equivalent binary trees - Easy Solution using Recursion - Beats 100 % ✌️🔜
Intuition\n1. If the left and right subtree\'s node are equal, then their subtree are checked and hence if the flipping may occur at the lowest subtree, so we c
# Intuition\n1. If the left and right subtree\'s node are equal, then their subtree are checked and hence if the flipping may occur at the lowest subtree, so we consider both flipping and non-flipping case here.\n\n1. And if either of them becomes true, then the Tree X is the flip Equivalent of the tree Y.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n**Edge case or Base Condition**:\n   If both tree\'s root are null, then return true since both tree are equivalent trees and if either of them is null, then one tree X cannot be equivalent to the other tree Y.\n\n    if(root1==null && root2==null)\n        return true;\n    else if(root1==null || root2==null)\n        return false;\n  \n  If in root value itself , both are unequal, then the Tree X cannot be the flipEquivalent of the Tree Y at any times.\n\n    if(root1.val!=root2.val)\n        return false;\n\n**Recursive Call**:\n   The flipEquiv function is called with doing no flip as the flip may occur in the lowest depth subtree also. Until then no flip can be done. Hence flipEquiv is called with root1.left, root2.left and then root1.right and root2.right.\n\n    boolean noflip=flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right);\n\n   The same flipEquiv function is called with doing flip since the flip can even occur immediately the next level of root node also.Hence the flip is done immediately and then the flipEquiv is called with root1.left,root2.right and then root1.right and root2.left.\n   \n    boolean flip=flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left);\n\n**Determine the flipEquiv**:\n   If either of them are true, then the Tree X is the flip Equivalent of the Tree Y.\n  \n    return noflip || flip;  \n   \n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- ***Time complexity***: **O(n)**.\n    n -> total number of nodes in the binary trees.\n\n**Traversal of Nodes**: **O(n)**.\n   Each node is visited exactly once when it recursively traverse both the binary trees.\n\n**Comparision at each node**: **O(2n)**.\n  At each node, it compares values and recursively check both the left and the right subtrees for equivalence, This results in two recursive call for each node.\n\n**Overall Time Complexity**: **O(n)**.\n   Since every node is processed once, the overall time complexity is proportional to the total number of nodes in the trees denoted as n.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- ***Space complexity***: **O(n)**.\n     n -> total number of nodes in the binary trees.\n\n**Recursive Stack**:\n   Space complexity is determined by the depth of the recursive stack, where that is proportional to the depth of the binary trees.\n\n**Worst Case(Unbalanced)**: **O(n)**.\n   In worst case, tree is completely unbalanced and its depth is equal to n.Hence the recursive stack will use **O(n) space**.\n\n**Best Case(balanced)** : **O(logn)**.\n  In the best case scenario, where the tree is perfectly balanced , the depth of the recursive stack will be proportional to the height of binary tree and is **O(logn)**.\n\n**Overall Space Complexity**:\n  **O(n)** -> for unbalanced tree(worst case).\n  **O(log n)** -> for balanced tree (best case).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        //choose any node : swap left and right child subtrees\n        if(root1==null && root2==null)\n          return true;\n        else if(root1==null || root2==null)\n          return false;\n        if(root1.val!=root2.val)\n          return false;\n        boolean noflip=flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right);\n        boolean flip=flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left);\n\n        return noflip || flip;\n    }\n}\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Java']