🌟 Beats 100.00% 👏 || Explained with example
\n# Intuition\n Describe your first thoughts on how to solve this problem. \nFlip Equivalent Binary Trees, asks you to determine if two binary trees are "flip e
\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFlip Equivalent Binary Trees, asks you to determine if two binary trees are "flip equivalent." Two trees are considered flip equivalent if they are either:\n\nStructurally identical.\nIdentical after flipping any number of nodes\' children.\nFlipping means swapping the left and right children of a node.\n\nWe will use recursion to solve this problem. The idea is simple: for any two nodes in the two trees (node1 in root1 and node2 in root2):\n\nIf both nodes are null, they are trivially equivalent.\nIf one node is null and the other is not, or their values are different, they can\'t be equivalent.\nOtherwise, we recursively check two possibilities:\nWithout flipping: The left child of node1 is equivalent to the left child of node2, and the right child of node1 is equivalent to the right child of node2.\nWith flipping: The left child of node1 is equivalent to the right child of node2, and the right child of node1 is equivalent to the left child of node2.\nIf one of these two possibilities is true for every node, the trees are flip equivalent.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nConsider two trees, root1 and root2:\n\n```\nroot1:                  root2:\n      1                       1\n     / \\                     / \\\n    2   3                   3   2\n   / \\                       / \\\n  4   5                     5   4\n     / \\                   / \\\n    6   7                 7   6\n```\nThese two trees are flip equivalent because:\n\nThe roots (1) are the same.\nWe need to flip the children of root nodes:\nAfter flipping, the left child of root1 (2) becomes comparable with the right child of root2 (2).\nSimilarly, the right child of root1 (3) becomes comparable with the left child of root2 (3).\nThis process continues recursively until all nodes are either matched directly or via flipping.\nWalkthrough:\nInitial Call:\n\nchecker(root1, root2) is called where both nodes have value 1. Since they are equal, we proceed to check their children.\nComparing Left and Right Children of the Roots:\n\nWithout flipping: Compare root1.left (2) with root2.left (3). They are not equal.\nWith flipping: Compare root1.left (2) with root2.right (2). They are equal, so we now recursively compare their children.\nRecursively Comparing Children of 2 Nodes:\n\nWe now compare root1.left.left (4) with root2.right.left (4). They are equal, and both have no further children, so this check is valid.\nNext, compare root1.left.right (5) with root2.right.right (5). They are equal, so we recursively check their children:\nCompare 5\'s left child (6) with 5\'s left child (7). They are not equal.\nFlip and compare 5\'s left child (6) with 5\'s right child (6). They are equal, so this check is valid.\nComparing the Right Subtree:\n\nAfter flipping, we compare root1.right (3) with root2.left (3). They are equal, and both have no further children, so this check is valid.\nSince all checks are satisfied, the trees are flip equivalent.\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n![upvote.jpeg](https://assets.leetcode.com/users/images/1944748d-800c-4a8e-ac0c-cba1bb87f69a_1729742982.6834853.jpeg)\n\n# Code\n```javascript []\n\nvar flipEquiv = function (root1, root2) {\n\n    let res = true\n\n    function checker(node1, node2) {\n\n        if (!node1 && !node2) return true\n\n        if (!node1 || !node2 || node1.val != node2.val) return false\n        \n        return ((checker(node1.left, node2.left) || checker(node1.left, node2.right)) && (checker(node1.right, node2.right) || checker(node1.right, node2.left)))\n\n    }\n\n    return checker(root1, root2)\n};\n```\n```python []\nclass Solution:\n    def flipEquiv(self, root1, root2):\n        \n        def checker(node1, node2):\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            return ((checker(node1.left, node2.left) or checker(node1.left, node2.right)) and\n                    (checker(node1.right, node2.right) or checker(node1.right, node2.left)))\n        \n        return checker(root1, root2)\n\n```\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```c []\n#include <stdbool.h>\n\n\n\nbool checker(struct TreeNode* node1, struct TreeNode* node2) {\n    if (!node1 && !node2) return true;\n    if (!node1 || !node2 || node1->val != node2->val) return false;\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\nbool flipEquiv(struct TreeNode* root1, struct TreeNode* root2) {\n    return checker(root1, root2);\n}\n```\n```c++ []\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        return checker(root1, root2);\n    }\n\nprivate:\n    bool checker(TreeNode* node1, TreeNode* node2) {\n        if (!node1 && !node2) return true;\n        if (!node1 || !node2 || node1->val != node2->val) return false;\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
['Tree', 'Depth-First Search', 'C', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']