🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n---\n\n# Intuition\nThe problem asks to determine if two binary trees are equivalent either directly or by flipping their left and right children. We need t
![image.png](https://assets.leetcode.com/users/images/57d2f5ad-e491-464f-9623-bd22808fb551_1729747899.3200066.png)\n\n---\n\n# Intuition\nThe problem asks to determine if two binary trees are equivalent either directly or by flipping their left and right children. We need to recursively check whether the subtrees are equal or flipped versions of each other. \n\n# Approach\n1. Perform a recursive traversal of both trees.\n2. For each pair of nodes (one from each tree):\n   - If both nodes are null, they are equivalent.\n   - If one node is null and the other is not, or their values differ, they are not equivalent.\n   - Otherwise, check if their children are equivalent in two cases:\n     - Without flipping: left subtrees match and right subtrees match.\n     - With flipping: left subtree of one matches the right subtree of the other and vice versa.\n\n# Complexity\n- Time complexity:  \n  $$O(n)$$ where n is the number of nodes in the smaller tree, because we traverse each node once.\n  \n- Space complexity:  \n  $$O(h)$$ where h is the height of the tree, because of the recursion stack.\n\n# Code\n\n```dart []\n/**\n * Definition for a binary tree node.\n * class TreeNode {\n *   int val;\n *   TreeNode? left;\n *   TreeNode? right;\n *   TreeNode([this.val = 0, this.left, this.right]);\n * }\n */\n\nclass Solution {\n  bool flipEquiv(TreeNode? root1, TreeNode? root2) {\n    return checker(root1, root2);\n  }\n\n  bool 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\n```python []\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\nclass Solution:\n    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:\n        return self.checker(root1, root2)\n\n    def checker(self, node1: TreeNode, node2: TreeNode) -> bool:\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        return (self.checker(node1.left, node2.left) and self.checker(node1.right, node2.right)) or \\\n               (self.checker(node1.left, node2.right) and self.checker(node1.right, node2.left))\n```\n\n```cpp []\n#include <iostream>\nusing namespace std;\n\nstruct TreeNode {\n    int val;\n    TreeNode *left;\n    TreeNode *right;\n    TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n};\n\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        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->right, node2->right)) || \n               (checker(node1->left, node2->right) && checker(node1->right, node2->left));\n    }\n};\n```\n\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        return checker(root1, root2);\n    }\n\n    private boolean checker(TreeNode node1, TreeNode node2) {\n        if (node1 == null && node2 == null) return true;\n        if (node1 == null || node2 == null || node1.val != node2.val) return false;\n\n        return (checker(node1.left, node2.left) && checker(node1.right, node2.right)) || \n               (checker(node1.left, node2.right) && checker(node1.right, node2.left));\n    }\n}\n```\n\n```javascript []\nfunction TreeNode(val, left = null, right = null) {\n  this.val = val;\n  this.left = left;\n  this.right = right;\n}\n\nvar flipEquiv = function(root1, root2) {\n  return checker(root1, root2);\n};\n\nfunction checker(node1, 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.right, node2.right)) ||\n         (checker(node1.left, node2.right) && checker(node1.right, node2.left));\n}\n```\n\n```csharp []\npublic class TreeNode {\n    public int val;\n    public TreeNode left;\n    public TreeNode right;\n    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n        this.val = val;\n        this.left = left;\n        this.right = right;\n    }\n}\n\npublic class Solution {\n    public bool FlipEquiv(TreeNode root1, TreeNode root2) {\n        return Checker(root1, root2);\n    }\n\n    private bool Checker(TreeNode node1, TreeNode node2) {\n        if (node1 == null && node2 == null) return true;\n        if (node1 == null || node2 == null || node1.val != node2.val) return false;\n\n        return (Checker(node1.left, node2.left) && Checker(node1.right, node2.right)) || \n               (Checker(node1.left, node2.right) && Checker(node1.right, node2.left));\n    }\n}\n```\n\n```go []\npackage main\n\ntype TreeNode struct {\n\tVal   int\n\tLeft  *TreeNode\n\tRight *TreeNode\n}\n\nfunc flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {\n\treturn checker(root1, root2)\n}\n\nfunc checker(node1 *TreeNode, node2 *TreeNode) bool {\n\tif node1 == nil && node2 == nil {\n\t\treturn true\n\t}\n\tif node1 == nil || node2 == nil || node1.Val != node2.Val {\n\t\treturn false\n\t}\n\n\treturn (checker(node1.Left, node2.Left) && checker(node1.Right, node2.Right)) || \n\t       (checker(node1.Left, node2.Right) && checker(node1.Right, node2.Left))\n}\n```\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Tree', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'C#', 'Dart']