951 · Flip Equivalent Binary Trees

Sub-variant B with a disjunction over two pairings. LC 100 tries one alignment, LC 101 tries the crossed one; this problem tries both and accepts either. The harder rep of the family.

1 — The problem

A flip swaps a node's two children. Can some sequence of flips turn tree a into tree b? Each node may be flipped or not, independently, so the search space is 2ⁿ — and the recursion prunes it to O(n).

Everything in the base cases is LC 100 verbatim. Only the last line changes:

Three problems, one machine, three ways of wiring the last line. If that reads as obvious, the sub-variant has transferred.

2 — Try one pairing, fall back to the other

At the root, the straight pairing fails immediately — a's left is 2 and b's left is 3. The flipped pairing then succeeds, and the same question repeats one level down.

2.1 Why this is O(n) and not 2ⁿ

The two alternatives look like branching, and a naive reading suggests every node doubles the work. It does not, because the value check on line 4 settles the choice before either branch is explored deeply.

• If a.left.val != b.left.val, the straight pairing dies at its own line 4 — one comparison, no descent.
• Values are distinct in this problem, so at most one of the two pairings can match on values. The other is rejected in O(1).
• So each node does O(1) failed work plus one real descent. Total O(n).

Remove the distinctness guarantee and the bound genuinely collapses — a tree of identical values makes both pairings viable at every node, and the recursion becomes exponential. That is a good follow-up answer to have ready.

2.2 The canonical-form alternative

A different framing: define a canonical orientation — at every node, put the smaller-valued child on the left — then two trees are flip equivalent exactly when their canonical forms are identical, which is LC 100. It is O(n), needs no disjunction, and generalises to "group all flip-equivalent trees" in a way the recursive version does not. Worth mentioning; not worth writing under time pressure.

3 — Complexity and edge cases

• Time O(n) with distinct values, space O(h).
• Both null: true. One null: false. Unchanged from LC 100.
• Identical trees: true, via the straight pairing, with the flipped one never evaluated — || short-circuits.
• Mirror images: true, via the flipped pairing at every node.
• A node with one child is where flipping is invisible: its single child can sit on either side and the tree is the same shape logically. The base cases handle it — the straight pairing pits the child against null and fails, the flipped one succeeds.
• Common bug: using && between the two alternatives instead of ||. That demands both pairings hold, which is only true for palindromic subtrees.
• Common bug: mis-bracketing — A && B || C && D happens to parse correctly in Java because && binds tighter, but write the parentheses anyway. The reader should not have to know the precedence table.

4 — Reference implementation

public boolean flipEquiv(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    if (a.val != b.val)            return false;
    return (flipEquiv(a.left, b.left)   && flipEquiv(a.right, b.right))   // no flip
        || (flipEquiv(a.left, b.right)  && flipEquiv(a.right, b.left));   // flip here
}