Flip Equivalent Binary Trees

Intuition

Flip equivalence is decided top-down: two trees can be aligned only if their roots hold the same value, and then their subtrees can be paired up in one of two ways. Either the left of one matches the left of the other and the rights match too, or a flip is applied so that left matches right and right matches left. Because node values are unique within a tree, we never have to worry about ambiguous pairings, and a greedy either/or check at each node is sufficient. The recursion bottoms out when both nodes are null (equivalent) or when exactly one is null or values differ (not equivalent). Each pair of nodes is compared once, so the algorithm runs in time proportional to the tree size.

Algorithm walkthrough

1. 1If both nodes are null, the (empty) subtrees are flip equivalent, return true.
2. 2If exactly one node is null, or the two values differ, return false.
3. 3Compute the no-flip case: left children match and right children match.
4. 4Compute the flip case: root1's left matches root2's right and root1's right matches root2's left.
5. 5Return true if either the no-flip case or the flip case holds.
6. 6The top-level call returns the answer for the whole trees.

Implementation

class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None and root2 is None:
            return True
        if root1 is None or root2 is None or root1.val != root2.val:
            return False
        no_flip = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
        flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)
        return no_flip or flip