Flip Equivalent Binary Trees: Recursive Tree Comparison

You are given the roots of two binary trees root1 and root2. A binary tree X is flip equivalent to a binary tree Y if you can make X equal to Y by flipping some nodes. Flipping a node means swapping its left and right children. Return True if the two trees are flip equivalent, or False otherwise.

This is LeetCode 951: Flip Equivalent Binary Trees, and it is a clean extension of the "compare two trees" pattern you see in Same Tree. The twist is that at each node, children can match in either order. They might line up directly, or they might line up after a flip.

Why this problem matters

Most tree comparison problems ask a binary question: do these two nodes match, yes or no? Flip Equivalent Trees adds a second dimension. At every node, you have two ways the children could align. That "try both orderings" logic makes this problem a natural stepping stone between simple comparisons (Same Tree, Symmetric Tree) and more complex structural matching.

The recursive pattern here also shows up in problems where you need to match subtrees with some flexibility, not just exact correspondence. Once you internalize the idea of branching into two possible recursive calls and combining them with or, you unlock a whole family of tree comparison problems.

Brute force approach

A naive approach would be to generate all possible flipped versions of one tree and check if any of them exactly matches the other tree. With n nodes, each node can be flipped or not, giving 2^n possible trees. Comparing each against the second tree takes O(n) time.

def flip_equiv_brute(root1, root2):
    if not root1 and not root2:
        return True
    if not root1 or not root2:
        return False
    if root1.val != root2.val:
        return False
    # Try all combinations by explicitly flipping
    # This generates exponentially many trees
    root1.left, root1.right = root1.right, root1.left
    flipped = is_same_tree(root1, root2)
    root1.left, root1.right = root1.right, root1.left
    unflipped = is_same_tree(root1, root2)
    return flipped or unflipped

This works but is wasteful. You do not need to physically flip and check entire trees. You can decide at each node whether to flip or not, without modifying anything.

The key insight

At each node, you have exactly two options for how the children could correspond:

1. Direct match: root1.left matches root2.left AND root1.right matches root2.right.
2. Flipped match: root1.left matches root2.right AND root1.right matches root2.left.

If either option works, the subtrees are flip-equivalent. You never need to actually flip anything. You just check both orderings recursively.

This turns an exponential brute force into a clean O(n) recursion. At each node you do constant work (compare values, try two pairings), and each node is visited exactly once.

Visual walkthrough

Let's trace through the recursion comparing root1 = [1, 2, 3, 4, 5, null, 6, null, null, 7, 8] and root2 = [1, 3, 2, 6, null, 5, 4, null, null, 8, 7] step by step.

Notice the pattern: at each node, you compare values first. If they match, you try both child orderings. The moment one ordering works (either direct or flipped), you recurse into that pairing. When all recursive calls return True, the entire tree is flip-equivalent.

The solution

def flip_equiv(root1, root2):
    if not root1 and not root2:
        return True
    if not root1 or not root2:
        return False
    if root1.val != root2.val:
        return False
    direct = flip_equiv(root1.left, root2.left) and flip_equiv(root1.right, root2.right)
    flipped = flip_equiv(root1.left, root2.right) and flip_equiv(root1.right, root2.left)
    return direct or flipped

Let's break this down:

• if not root1 and not root2: return True is the base case. Two empty nodes are trivially flip-equivalent. This is where every recursive path eventually bottoms out.
• if not root1 or not root2: return False catches the case where one tree has a node and the other has nothing. They cannot match.
• if root1.val != root2.val: return False checks the values. If the current nodes have different values, no amount of flipping can fix that.
• direct checks whether children align without flipping: left with left, right with right.
• flipped checks whether children align with flipping: left with right, right with left.
• return direct or flipped returns True if either ordering works. You only need one valid alignment.

Complexity analysis

Time is O(n), where n is the number of nodes in the smaller tree. At each node, you do O(1) work (compare values) and then recurse. In the worst case, both the direct and flipped paths need to be explored, but even then each node is visited a constant number of times.

Space is O(h), where h is the height of the tree, because of the recursive call stack. For a balanced tree, h = log(n). For a completely skewed tree, h = n.

Building blocks

This problem is built on two fundamental bricks:

1. Parallel tree recursion (double-null base case). The three-way base case, both null returns True, one null returns False, values differ returns False, is the same template you write in Same Tree, Symmetric Tree, and every "compare two tree nodes" function. You recurse into two nodes simultaneously.

if not a and not b:
    return True
if not a or not b:
    return False
if a.val != b.val:
    return False

2. Branching match with or. Instead of a single recursive pairing (left, left and right, right), you try two pairings and accept either one. This "try both orderings" pattern is specific to problems where structural flexibility exists, like flip equivalence.

direct = solve(a.left, b.left) and solve(a.right, b.right)
flipped = solve(a.left, b.right) and solve(a.right, b.left)
return direct or flipped

Edge cases to watch for

• Both trees are empty (both roots are None): return True. Two empty trees are trivially flip-equivalent.
• One tree is empty and the other is not: return False. The "one null" check catches this on the first call.
• Single nodes with the same value: return True. Both children are null on both sides, so the "both null" base case handles it.
• Trees with the same structure and values (no flips needed): the direct check returns True without ever trying the flipped pairing.
• Trees that require flips at every level: the recursion naturally handles this. Each level tries both orderings independently.
• Different values at the root: return False immediately. No recursion needed.

Common mistakes

Forgetting the flipped pairing. If you only check (left, left) and (right, right), you are solving Same Tree, not Flip Equivalent Trees. The whole point is the or flipped branch.

Physically flipping nodes. You do not need to modify either tree. The recursion checks both orderings without any structural changes. Swapping children adds unnecessary complexity and can cause bugs if you forget to swap back.

Checking all four combinations independently. Some people try all four pairings: (left, left), (left, right), (right, left), (right, right). That is too many. The two valid pairings are "direct" (both children match in order) and "flipped" (both children match swapped). You cannot mix and match one child direct and the other flipped.

From understanding to recall

You just traced through a recursive solution that checks two possible child orderings at each node. The base cases are the same as Same Tree. The new piece is the or flipped branch. It makes sense right now. But will you remember to try both pairings when you see a similar problem next month?

Understanding is the first step. Recall under pressure is the second. Spaced repetition bridges the gap. You type the solution from scratch at increasing intervals: after one day, then three days, then a week. Each time, you reconstruct the double-null base case, the value check, and the two recursive pairings from memory.

The parallel tree recursion pattern and the branching match pattern together cover a wide range of tree comparison problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Same Tree - The foundation for this problem, using the same double-null base case but with only one pairing
• Symmetric Tree - Another variation that compares mirror pairs instead of corresponding pairs
• Invert Binary Tree - A related tree transformation problem where you actually perform the flips