951. Flip Equivalent Binary Trees - Explanation

Problem Link



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Binary Trees - Understanding tree structure with left and right children
  • Tree Traversal (DFS/BFS) - Visiting nodes recursively or iteratively using stacks/queues
  • Recursion - Comparing subtrees and handling base cases with null nodes

Intuition

Two trees are flip equivalent if we can make them identical by swapping the left and right children of some nodes. At each node, the subtrees either match directly (left with left, right with right) or match when flipped (left with right, right with left). We recursively check both possibilities.

Algorithm

  1. Base case: If either node is null, return true only if both are null.
  2. If the values of the two nodes differ, return false.
  3. Recursively check two scenarios:
    • No flip: left subtrees match AND right subtrees match.
    • Flip: left of tree1 matches right of tree2 AND right of tree1 matches left of tree2.
  4. Return true if either scenario succeeds.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if not root1 or not root2:
            return not root1 and not root2
        if root1.val != root2.val:
            return False

        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)
            )

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n) for recursion stack.

Intuition

We can solve this iteratively using a queue to process node pairs level by level. For each pair of nodes, we check if their values match. Then we determine whether to compare children directly or in flipped order by checking which pairing makes the left children's values match.

Algorithm

  1. Initialize a queue with the pair (root1, root2).
  2. While the queue is not empty:
    • Dequeue a pair of nodes.
    • If either is null, check that both are null. If not, return false.
    • If their values differ, return false.
    • Determine child pairing: if both left children exist and have equal values, or both are null, pair children directly. Otherwise, pair them in flipped order.
    • Enqueue the appropriate child pairs.
  3. Return true if all pairs are processed successfully.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        q = deque([(root1, root2)])

        while q:
            node1, node2 = q.popleft()
            if not node1 or not node2:
                if node1 != node2:
                    return False
                continue

            if node1.val != node2.val:
                return False

            if ((node1.right and node2.right and
                 node1.right.val == node2.right.val) or
                (not node1.right and not node2.right)
            ):
                q.append((node1.left, node2.left))
                q.append((node1.right, node2.right))
            else:
                q.append((node1.left, node2.right))
                q.append((node1.right, node2.left))

        return True

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Iterative DFS

Intuition

This is the iterative version of the recursive DFS approach, using an explicit stack instead of the call stack. We process node pairs from the stack, checking values and pushing child pairs in the appropriate order (direct or flipped).

Algorithm

  1. Initialize a stack with the pair (root1, root2).
  2. While the stack is not empty:
    • Pop a pair of nodes.
    • If either is null, verify both are null. If not, return false.
    • If their values differ, return false.
    • Determine child pairing: if left children match (both null or same value), push direct pairs. Otherwise, push flipped pairs.
  3. Return true if all pairs are processed successfully.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        stack = [(root1, root2)]

        while stack:
            node1, node2 = stack.pop()

            if not node1 or not node2:
                if node1 != node2:
                    return False
                continue

            if node1.val != node2.val:
                return False

            if ((node1.left and node2.left and
                 node1.left.val == node2.left.val) or
                (not node1.left and not node2.left)
            ):
                stack.append((node1.left, node2.left))
                stack.append((node1.right, node2.right))
            else:
                stack.append((node1.left, node2.right))
                stack.append((node1.right, node2.left))

        return True

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

Common Pitfalls

Forgetting to Check Both Flip Orderings

A common mistake is only checking if the trees match directly without considering the flipped case. The problem allows flipping at any node, so you must check both scenarios: (1) left matches left AND right matches right, OR (2) left matches right AND right matches left. Missing either case will produce incorrect results.

Incorrect Null Handling in Base Cases

When comparing nodes, both null checks must be handled carefully. If only one node is null (but not both), the trees cannot be equivalent. Returning true when only one is null, or forgetting to handle the case where both are null, leads to incorrect behavior.

Not Checking Node Values Before Recursing

Before exploring children, you must verify that the current nodes have the same value. Skipping this check and directly comparing children can cause false positives when nodes at the same position have different values but happen to have structurally similar subtrees.