⚡Flashcard Drill➔
NeetCode #452LC-951MediumTrees
← Back to All Problems

#452 · #951 · Flip Equivalent Binary Trees(翻转等价二叉树)

📌 Problem Statement & Constraints

For a binary tree T, a flip swaps a node's left and right children. Two trees are flip equivalent if one can be made identical to the other by a series of flips. Given two roots, return whether they are flip equivalent. Constraints: the number of nodes in each tree is in [0, 100], 0 <= Node.val <= 99.

💡 Core Algorithmic Approaches

  1. At each node, the two subtrees may match either directly or after a flip.
  2. So the check is: the values match, and (left~left and right~right) or (left~right and right~left).
  3. The base cases are both None (equivalent) and exactly one None (not equivalent).
  4. This is O(min(n, m)) with early exit.

💻 Benchmark Python3 Implementation

class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if not root1 and not root2:
            return True                    # both empty
        if not root1 or not root2:
            return False                   # only one is empty
        if root1.val != root2.val:
            return False
        # either the subtrees match directly, or after one flip
        return ((self.flipEquiv(root1.left, root2.left)
                 and self.flipEquiv(root1.right, root2.right))
                or (self.flipEquiv(root1.left, root2.right)
                    and self.flipEquiv(root1.right, root2.left)))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(min(n, m)): the recursion stops at the first mismatch.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Only trying the unflipped pairing: flips are allowed at every node, so both pairings must be attempted.
  • Forgetting the exactly one None case: it would dereference None.
  • Actually mutating the trees with flips: the check is structural; no mutation is needed.
  • Assuming the trees must have the same shape: flips change the shape while preserving the value multiset and the equivalence relation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems