Flip Equivalent Binary Trees 🗿| Easy & Clean Code | Easy Explaination ✅ | Beats 100% ✅ | Java | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe idea is to recursively compare two trees. \nTwo Trees are considered to be flip equ
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe idea is to recursively compare two trees. \nTwo Trees are considered to be flip equivalent if they are either identical or can be identical after flipping the left and right subtrees at any level. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. If both roots are null, then we can say trees are equal so return true.\n2. If one tree is null and other is not , return false because one tree has node/nodes where other don\'t which means they are not identical.\n3. Recursively check if: \n    -  The left child of root1 matches the left child of root2 and the right child of root1 matches right child of root2(without flipping).\n    - The left child of root1 matches the right child of root2 and right child of root1 matches with the left child of root2(afterflipping).\n5. Return true either of the above conditions holds.  \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n```\nO(n) : we are visiting every node exactly once.\nn is the number of nodes in tree.\n```\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n```\nO(h)\n```\n`where h is height tree`\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        if(root1 == null && root2 == null) return true;\n        if(root1 == null || root2 == null) return false;\n        if(root1.val != root2.val) return false;\n        boolean withoutSwapping = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);\n        boolean afterSwap = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);\n        return withoutSwapping || afterSwap;\n    }\n}\n```\n```C++ []\n    class Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if(root1 == nullptr && root2 == nullptr) return true;\n        if(root1 == nullptr || root2 == nullptr) return false;\n        if(root1 -> val != root2 -> val) return false;\n        bool withoutSwapping = flipEquiv(root1 -> left, root2 -> left) && flipEquiv(root1 -> right, root2 -> right);\n        bool afterSwap = flipEquiv(root1 -> left, root2 -> right) && flipEquiv(root1 -> right, root2 -> left);\n        return withoutSwapping || afterSwap;\n    }\n};\n```\n
['Tree', 'Depth-First Search', 'C++', 'Java']