DDSA Solutions

951. Flip Equivalent Binary Trees

MediumView on LeetCode
TreeDepth-First SearchBinary Tree
Time: O(n)
Space: O(n)

Problem Overview

Two trees are flip-equivalent if one can be made identical to the other by flipping some node children.

Intuition

Two trees are flip-equivalent if one can be made identical to the other by flipping some node children.

Algorithm

  1. 1DFS: base cases (both null, one null, different values).
  2. 2Return (flipEquiv(l1,l2) && flipEquiv(r1,r2)) || (flipEquiv(l1,r2) && flipEquiv(r1,l2)).

Common Pitfalls

  • •Check both direct and flipped child combinations.
951.cs
C#
// Approach: Recursive equivalence check; two trees are flip-equivalent if they match directly or after swapping children at any node.
// Time: O(n) Space: O(n)

public class TreeNode(TreeNode root1, TreeNode root2)
    {
        if (root1 == null)
            return root2 == null;
        if (root2 == null)
            return root1 == null;
        if (root1.val != root2.val)
            return false;
        return //
            FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right) ||
            FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left);
    }
}
Was this solution helpful?

Related Problems