Leetcode 0951. Flip Equivalent Binary Trees

Problem statement

https://leetcode.com/problems/flip-equivalent-binary-trees/

Solution

We can solve this problem recursively:

1. if we have None for both trees, or equal values, return True.
2. If we have one None and one node, return False
3. Run recursively for two cases, when we flip and when we not.

Complexity

It is O(n + m) for time and O(max(h1, h2)) for space.

Code

class Solution:
    def flipEquiv(self, root1, root2):
        if not root1 and not root2: return True
        if (root1 and not root2) or (root2 and not root1): return False
        
        if root1.val != root2.val: return False
        
        if self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right):
            return True
        
        if self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left):
            return True
        
        return False