Beats 100%|| Detailed and easy to understand Explanation||
Intuition\nA flip operation allows us to swap the left and right children of any node in the tree. The trees are considered "flip equivalent" if we can make one
# Intuition\nA flip operation allows us to swap the left and right children of any node in the tree. The trees are considered "flip equivalent" if we can make one tree equal to the other by flipping nodes.\n\nIf two trees are flip equivalent:\n\n1. Their root values must be the same.\n2. The left subtree of one tree must be equivalent to either the left or right subtree of the other tree, and the same goes for the right subtree.\n\nThe problem can be recursively solved by checking both possible matches (flip or no flip) for each subtree.\n\n# Approach\n- Recursive function:\n\n- Start from the roots of both trees. If both are null, return true (both trees are empty). If one is null and the other is not, return false.\n- If the values of the current nodes do not match, return false.\n\n- Recursively check both subtrees:\n1. Check if the left subtree of the first tree is equivalent to the left subtree of the second tree, and the right subtree is equivalent to the right subtree (no flip).\n1. Check if the left subtree of the first tree is equivalent to the right subtree of the second tree, and the right subtree is equivalent to the left subtree (flip).\n\n- If either of these conditions is satisfied, return true. Otherwise, return false.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(h)\n\n# Code\n```java []\nclass Solution {\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        \n        return checker(root1, root2);\n    }\n\n    private boolean checker(TreeNode node1, TreeNode node2) {\n        if (node1 == null && node2 == null) {\n            return true;\n        }\n        if (node1 == null || node2 == null || node1.val != node2.val) {\n            return false;\n        }\n\n        return (checker(node1.left, node2.left) || checker(node1.left, node2.right)) &&\n               (checker(node1.right, node2.right) || checker(node1.right, node2.left));\n    }\n}\n```\n\n```Python []\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n        return self.checker(root1, root2)\n    \n    def checker(self, node1: Optional[TreeNode], node2: Optional[TreeNode]) -> bool:\n        # Base cases\n        if not node1 and not node2:\n            return True\n        if not node1 or not node2 or node1.val != node2.val:\n            return False\n        \n        # Recursively check the children (flipped and non-flipped)\n        return (self.checker(node1.left, node2.left) or self.checker(node1.left, node2.right)) and \\\n               (self.checker(node1.right, node2.right) or self.checker(node1.right, node2.left))\n\n```\n```Cpp []\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        return checker(root1, root2);\n    }\n\n    bool checker(TreeNode* node1, TreeNode* node2) {\n        // Base cases\n        if (node1 == nullptr && node2 == nullptr) {\n            return true;\n        }\n        if (node1 == nullptr || node2 == nullptr || node1->val != node2->val) {\n            return false;\n        }\n\n        // Recursively check children (flipped and non-flipped)\n        return (checker(node1->left, node2->left) || checker(node1->left, node2->right)) &&\n               (checker(node1->right, node2->right) || checker(node1->right, node2->left));\n    }\n};\n\n```\n\n\n# Detailed Java code Breakdown:\n\n```\nclass Solution {\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        return checker(root1, root2);\n    }\n```\nWe define a public class Solution that contains a method flipEquiv. This method accepts two parameters:\n\n- TreeNode root1: the root of the first tree.\n- TreeNode root2: the root of the second tree.\n\nThe method simply calls the helper function checker with the two root nodes as arguments and returns its result. This means the actual checking is done in the helper function checker.\n\nThen,\n\n```\n    private boolean checker(TreeNode node1, TreeNode node2) {\n        if (node1 == null && node2 == null) {\n            return true;\n        }\n        if (node1 == null || node2 == null || node1.val != node2.val) {\n            return false;\n        }\n\n```\n\nHere, we define the recursive helper method checker to determine whether two subtrees (starting at node1 and node2) are flip equivalent.\n\n1. First condition:\n\n- If both node1 and node2 are null, you return true. This means that if both trees/subtrees are empty, they are trivially flip equivalent.\n\n2. Second condition:\n\n- If either node1 or node2 is null (but not both), or their values do not match (node1.val != node2.val), then the trees are not flip equivalent. In this case, you return false.\n\nThis ensures that trees cannot be equivalent if they don\u2019t have the same root value or one is null while the other isn\u2019t.\n\n```\n        return (checker(node1.left, node2.left) || checker(node1.left, node2.right)) &&\n               (checker(node1.right, node2.right) || checker(node1.right, node2.left));\n    }\n}\n\n\n```\nThis is where the recursive checking happens. The goal is to check both possibilities at each node:\n\n- Either the children are in the same order (no flip), or they are flipped (left child of one corresponds to the right child of the other).\n\n**Let\'s breakdown logic:**\n1. First part of the return statement:\n`(checker(node1.left, node2.left) || checker(node1.left, node2.right))\n`\n- You recursively check if the left child of node1 is equivalent to the left child of node2 (no flip), or the left child of node1 is equivalent to the right child of node2 (flip).\n\nThis ensures you handle both possibilities for the left subtree\n\n2. Second part of the return statement:\n`(checker(node1.right, node2.right) || checker(node1.right, node2.left))\n`\n\n- Similarly, you recursively check if the right child of node1 is equivalent to the right child of node2 (no flip), or the right child of node1 is equivalent to the left child of node2 (flip).\n\nThis ensures you handle both possibilities for the right subtree.\n\n- Combined logic:\nFor the trees to be flip equivalent, both the left and right subtrees must be equivalent in one of the two configurations (either flipped or not).\n\n- Why return this combination?\nThe && operator ensures that both the left and right subtrees of the current node are equivalent in some configuration (either flipped or not). If either side fails the equivalency test, the entire subtree fails.\n\n\n![wb829ok5jtuc1.jpeg](https://assets.leetcode.com/users/images/92432d03-3971-47da-87b8-a6d9a395600c_1729789141.1738553.jpeg)\n\n\n\n\n\n
['C++', 'Java', 'Python3']