C# Solution with recursion. (Read description for complexities)
Time Complexity:  O(min(M,N)) where M and N are number of nodes in each tree.\n                            Reason: In worst case we need to check all the nodes,
Time Complexity:  O(min(M,N)) where M and N are number of nodes in each tree.\n                            Reason: In worst case we need to check all the nodes, but untill we exhaust all the nodes of the minimum size tree.\nSpace Complexity: O(min(H1,H2)), where H1 and H2 are the height of trees or O(min(M,N)) in the worst case. \n                            Reason: The space is need for the stack in recursion. In worst case a tree can be a single branch where the hight is equal to the size of the tree. Hence the space complexity can be O(min(M,N)) where M and N are number of nodes in each tree. \n\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int x) { val = x; }\n * }\n */\npublic class Solution\n{\n    public bool FlipEquiv(TreeNode root1, TreeNode root2)\n    {\n        if (root1 == root2) return true;\n        if (root1 == null || root2 == null || root1.val != root2.val) return false;\n        \n        return  FlipEquiv(root1.left,root2.left) &&    // The precedence of && is greater than ||\n                FlipEquiv(root1.right,root2.right) ||\n                FlipEquiv(root1.right,root2.left) && \n                FlipEquiv(root1.left,root2.right);\n    }\n}\n```
[]