LeetCode 951: Flip Equivalent Binary Trees

Problem Restatement

We are given the roots of two binary trees, root1 and root2.

A flip operation chooses one node and swaps its left and right child subtrees.

Two trees are flip equivalent if we can make them equal after doing zero or more flip operations.

Return true if the two trees are flip equivalent. Otherwise, return false.

The official constraints say each tree has between 0 and 100 nodes, and each tree has unique node values in the range [0, 99].

Input and Output

Example function shape:

def flipEquiv(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    ...

Examples

Example 1:

root1 = [1,2,3,4,5,6,None,None,None,7,8]
root2 = [1,3,2,None,6,4,5,None,None,None,None,8,7]

Output:

True

These trees can be made equal by flipping some nodes. The LeetCode example says the flips happen at nodes with values 1, 3, and 5.

Example 2:

root1 = []
root2 = []

Output:

True

Two empty trees are equivalent.

Example 3:

root1 = []
root2 = [1]

Output:

False

One tree is empty and the other is not, so they cannot be equivalent.

First Thought: Direct Tree Comparison

If flips were not allowed, this would be the same as checking whether two trees are identical.

For each pair of nodes, we would check:

root1.val == root2.val

Then we would compare:

root1.left  with root2.left
root1.right with root2.right

But this is not enough here.

Because flips are allowed, the left child of one tree may match the right child of the other tree.

So at each pair of nodes, there are two valid possibilities.

Key Insight

For two nodes to be flip equivalent, three things must hold.

First, both nodes must exist, or both must be None.

Second, if both nodes exist, their values must be equal.

Third, their children must match in one of two ways:

# No flip
root1.left  matches root2.left
root1.right matches root2.right

or:

# Flip
root1.left  matches root2.right
root1.right matches root2.left

This gives a natural recursive solution.

At every node, we recursively check both child arrangements. If either arrangement works, the current subtree pair is flip equivalent.

Algorithm

Use DFS recursion.

For every pair of nodes a and b:

1. If both are None, return True.
2. If only one is None, return False.
3. If a.val != b.val, return False.
4. Check the no-flip case.
5. Check the flip case.
6. Return True if either case works.

The recursive condition is:

same = dfs(a.left, b.left) and dfs(a.right, b.right)
flipped = dfs(a.left, b.right) and dfs(a.right, b.left)

return same or flipped

Correctness

We prove that the algorithm returns True exactly when the two trees are flip equivalent.

If both current nodes are None, the two empty subtrees are equal, so returning True is correct.

If exactly one current node is None, then one subtree has a node where the other has no node. No flip can create or remove nodes, so returning False is correct.

If both nodes exist but their values differ, no flip can change node values. Therefore, the two subtrees cannot become equal, so returning False is correct.

Now assume both nodes exist and have the same value. A flip at this node has only two possible outcomes. Either the children stay aligned directly, or the children are swapped. The algorithm checks both possibilities:

dfs(a.left, b.left) and dfs(a.right, b.right)

and:

dfs(a.left, b.right) and dfs(a.right, b.left)

If either condition is true, then the child subtrees can be made equal under the corresponding arrangement, so the current subtrees are flip equivalent.

If both conditions are false, then neither possible child arrangement can make the subtrees equal. Since a flip only swaps the two children, there is no third arrangement to try. Therefore, the current subtrees are not flip equivalent.

By applying this reasoning recursively to every pair of compared subtrees, the algorithm correctly decides whether the two whole trees are flip equivalent.

Complexity

Let n be the number of nodes in the trees.

Here, h is the height of the tree.

In the worst case, a skewed tree has height n, so the space complexity can be O(n).

For a balanced tree, the recursion depth is O(log n).

Implementation

# 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

from typing import Optional

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:
            return False

        if root1.val != root2.val:
            return False

        same = (
            self.flipEquiv(root1.left, root2.left)
            and self.flipEquiv(root1.right, root2.right)
        )

        flipped = (
            self.flipEquiv(root1.left, root2.right)
            and self.flipEquiv(root1.right, root2.left)
        )

        return same or flipped

Code Explanation

The first base case handles two empty subtrees:

if root1 is None and root2 is None:
    return True

Two empty subtrees are already equal.

The second base case handles shape mismatch:

if root1 is None or root2 is None:
    return False

If only one node exists, the subtrees cannot match.

Then we compare values:

if root1.val != root2.val:
    return False

A flip changes child positions only. It does not change values.

After that, we try the direct child pairing:

same = (
    self.flipEquiv(root1.left, root2.left)
    and self.flipEquiv(root1.right, root2.right)
)

This means no flip is needed at the current node.

Then we try the swapped child pairing:

flipped = (
    self.flipEquiv(root1.left, root2.right)
    and self.flipEquiv(root1.right, root2.left)
)

This means a flip is allowed at the current node.

Finally:

return same or flipped

The current subtrees are flip equivalent if either arrangement works.

Testing

For local testing, we can build trees from level-order arrays.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root1 = build_tree([1, 2, 3, 4, 5, 6, None, None, None, 7, 8])
    root2 = build_tree([1, 3, 2, None, 6, 4, 5, None, None, None, None, 8, 7])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([])
    root2 = build_tree([])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([])
    root2 = build_tree([1])
    assert s.flipEquiv(root1, root2) is False

    root1 = build_tree([1, 2, 3])
    root2 = build_tree([1, 3, 2])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([1, 2, None])
    root2 = build_tree([1, None, 2])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([1, 2, 3])
    root2 = build_tree([1, 2, 4])
    assert s.flipEquiv(root1, root2) is False

    print("all tests passed")

run_tests()

Test meaning: