Flip Equivalent Binary Trees
Mahabharata — The Flexible Formation — Two Trees Equal If We Allow Any Node to Flip Its Children
बच्चों को पलटने की अनुमति — फिर भी वही वृक्ष?। दो रास्ते — सीधा और पलटकर — दोनों जांचो॥
*Permission to flip children — yet the same tree? Two paths — direct and flipped — check both.*
The Story
Two binary trees are flip equivalent if one can be converted to the other by flipping (swapping children) any number of nodes. Check if they are flip equivalent.
For `root1=[1,2,3,4,5,6,null,null,null,7,8]` and `root2=[1,3,2,null,6,4,5,null,null,null,null,8,7]`: true.
**Recursive:** At each pair of corresponding nodes (r1, r2), there are two possibilities: 1. **No flip:** r1.left ↔ r2.left and r1.right ↔ r2.right 2. **Flip:** r1.left ↔ r2.right and r1.right ↔ r2.left
Both must be recursively true.
```java public boolean flipEquiv(TreeNode root1, TreeNode root2) { if (root1 == null && root2 == null) return true; if (root1 == null || root2 == null) return false; if (root1.val != root2.val) return false; // Option 1: No flip at this node boolean noFlip = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right); // Option 2: Flip at this node boolean flip = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left); return noFlip || flip; } ```
Trace for single level [1,2,3] and [1,3,2]: - root1=1, root2=1: 1==1 - noFlip: flipEquiv(2,3) → 2≠3 → false - flip: flipEquiv(2,2) && flipEquiv(3,3) → true && true = true - Return true ✓
The Same isSameTree Approach
isSameTree with allowance for child swaps. Already captured in the two-case recursion above.
// The recursive two-case approach IS the optimal solution.
// No simpler brute force exists for this problem.The Two-Case Flip Recursion
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null || root1.val != root2.val) return false;
boolean noFlip = flipEquiv(root1.left, root2.left)
&& flipEquiv(root1.right, root2.right);
boolean flip = flipEquiv(root1.left, root2.right)
&& flipEquiv(root1.right, root2.left);
return noFlip || flip;
}Step-by-Step Walkthrough
[1,null,2] vs [1,2,null] At 1==1: noFlip=flipEquiv(null,2)=false. flip=flipEquiv(null,null)&&flipEquiv(2,2)=true. Return true ✅
Deep Insight
**isSameTree vs flipEquiv:** - isSameTree: r1.left=r2.left and r1.right=r2.right (one case) - flipEquiv: (r1.left=r2.left and r1.right=r2.right) OR (r1.left=r2.right and r1.right=r2.left) (two cases)
flipEquiv is isSameTree with one additional case (the flip).
**Short-circuit optimization:** `noFlip || flip` short-circuits — if noFlip is true, flip is not computed. This saves time when no flips are needed.
**O(n) visits at most 2n pairs per level:** Due to the OR, each node pair is visited at most once from the successful branch. Total O(n).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(h) | O(h) call stack |
| Optimal | O(n) | O(h) | Each node pair visited at most once via successful path |
Pattern Recognition
✅ Flip equivalent = isSameTree with two-case at each node ✅ noFlip: parallel; flip: cross ✅ Return noFlip || flip ✅ Extend isSameTree by adding one more case **LeetCode Trigger Phrases:** → "flip equivalent binary trees" → Two trees equal allowing child swaps → Two-case recursive tree comparison
Bhagavad Gita 2.25
अव्यक्तो ऽयमचिन्त्योऽयमविकार्योऽयमुच्यते। तस्मादेवं विदित्वैनं नानुशोचितुमर्हसि॥
It is said that the Self is unmanifest, inconceivable, and unchangeable. Knowing it thus, you should not grieve.
Connection: Flip equivalent trees are structurally the same in essence despite appearing different on the surface — one might be a flipped version of the other. Like the unchanging Self that appears in different forms (bodies, genders, roles) yet remains the same essential truth, two flip-equivalent trees have the same intrinsic structure. Their apparent difference (which child is left, which is right) does not change their fundamental nature (the values and relationships).