Beats 100% | Easy Solution | DFS
\n# Intuition\n- The problem is to determine if two binary trees are flip equivalent. Two trees are considered flip equivalent if they are identical or can be m
![image.png](https://assets.leetcode.com/users/images/f9de66c2-d519-4d0c-a996-bb8f5cc68bb4_1729748150.2061234.png)\n# Intuition\n- The problem is to determine if two binary trees are flip equivalent. Two trees are considered flip equivalent if they are identical or can be made identical by flipping some of their subtrees. Specifically, at any node, we can choose to swap its left and right children, but this swap operation can be performed at any number of nodes and any number of times.\n\n# Approach\nThe recursive approach can be broken down as follows:\n\n1. Base Cases:\n    - If both root1 and root2 are null, they are trivially equivalent.\n    - If only one of the roots is null, or their values are different, they can\'t be equivalent.\n2. Recursive Check:\n    - For each node, there are two possibilities:\n        - No flip: The left child of root1 is equivalent to the left child of root2, and the right child of root1 is equivalent to the right child of root2.\n        - Flip: The left child of root1 is equivalent to the right child of root2, and the right child of root1 is equivalent to the left child of root2.\n        - The solution recursively checks both possibilities and returns true if either one is valid.\n# Complexity\n- Time Complexity: O(n), where n is the number of nodes in the trees. In the worst case, every node in both trees is visited once.\n- Space Complexity: O(h), where h is the height of the tree. This is the space required for the recursive stack. In the worst case, the height can be O(n), making the space complexity O(n).\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if(!root1 && !root2) return true;\n        if(!root1 || !root2) return false;\n        if(root1->val != root2->val) return false;\n\n        return (\n                (flipEquiv(root1->left,root2->left) || \n                    flipEquiv(root1->left,root2->right)) \n                    &&\n                (flipEquiv(root1->right,root2->left)  ||\n                    flipEquiv(root1->right,root2->right)) \n               );\n    }\n};\n```\n```Java []\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\n        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||\n               (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:\n        if not root1 and not root2:\n            return True\n        if not root1 or not root2:\n            return False\n        if root1.val != root2.val:\n            return False\n\n        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\n               (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))\n\n```\n```Javascript []\nvar flipEquiv = function(root1, root2) {\n    if (!root1 && !root2) return true;\n    if (!root1 || !root2 || root1.val !== root2.val) return false;\n\n    return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||\n           (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));\n};\n\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/e0fe9fda-eace-4fc7-88d3-61b6ce5e4ea3_1729748220.5560973.png)\n
['Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']