Pro

951. Flip Equivalent Binary Trees - Explanation

Problem Link

Description

A flip at a node exchanges its entire left and right subtrees. Return true if some sequence of flips can make the two binary trees identical, or false otherwise. You may flip any number of nodes, including none.

Flips change the ordering of children but preserve node values and parent-child relationships. Two empty trees are equivalent.

Each tree is encoded as a level-order array. After the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted. [] represents an empty tree.

Example 1:

Flip Equivalent Binary Trees, example 1: illustration of the example

Input: root1 = [8,3,6,1]
root2 = [8,6,3,null,null,null,1]

Output: true

Explanation: Flip the root to exchange the subtrees rooted at 3 and 6. Then flip node 3 so its child 1 moves from the left side to the right side. The first tree now matches the second.

Example 2:

Flip Equivalent Binary Trees, example 2: illustration of the example

Input: root1 = [8,3,6,1]
root2 = [8,3,6,null,null,1]

Output: false

Explanation: Node 1 is a child of node 3 in the first tree and of node 6 in the second. Flipping only swaps the two child positions of a node; it cannot change a child's parent, so these trees cannot match.

Example 3:

Flip Equivalent Binary Trees, example 3: illustration of the example

Input: root1 = []
root2 = []

Output: true

Explanation: Both trees are empty and already identical, so no flips are needed.

Constraints:

  • Each tree contains between 0 and 100 nodes.
  • 0 <= Node.val <= 99
  • Node values are unique within each tree.


Topics

Tree Binary Tree Depth-First Search

Company Tags

Please upgrade to NeetCode Pro to view company tags.



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.