# Flip Equivalent Binary Trees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flip-equivalent-binary-trees)
Canonical: https://scaleengineer.com/dsa/problems/flip-equivalent-binary-trees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Anduril](https://scaleengineer.com/companies/anduril)
---
## Problem
For a binary tree **T**, we can define a **flip operation** as follows: choose any node, and swap the left and right child subtrees.

A binary tree **X** is _flip equivalent_ to a binary tree **Y** if and only if we can make **X** equal to **Y** after some number of flip operations.

Given the roots of two binary trees `root1` and `root2`, return `true` if the two trees are flip equivalent or `false` otherwise.

**Example 1:**

![Flipped Trees Diagram](https://assets.glich.co/dsa/flip-equivalent-binary-trees/image0.png) 

**Input:** root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
**Output:** true
**Explanation:** We flipped at nodes with values 1, 3, and 5.

**Example 2:**

**Input:** root1 = [], root2 = []
**Output:** true

**Example 3:**

**Input:** root1 = [], root2 = [1]
**Output:** false

**Constraints:**

* The number of nodes in each tree is in the range `[0, 100]`.
* Each tree will have **unique node values** in the range `[0, 99]`.

# Approaches
## Canonical Representation Traversal
This approach involves converting each tree into a canonical string representation. Two trees are flip equivalent if and only if their canonical representations are identical. The canonical form is constructed recursively, ensuring that for any node, the representations of its children are ordered consistently (e.g., lexicographically). This makes the final representation independent of the initial left/right child arrangement.
**Time:** O(N1^2 + N2^2), where N1 and N2 are the number of nodes in the two trees. For each node in a tree of size N, we construct a string. The string length can be up to O(N), and string operations (concatenation, comparison) take time proportional to the length. This leads to a roughly O(N^2) complexity for processing one tree. · **Space:** O(N1^2 + N2^2), where N1 and N2 are the node counts. The recursion depth is O(H) (height), and at each of the N calls, we create new strings. The total size of strings stored in the call stack can be large, reaching O(N^2) for a skewed tree.
**Pros:** Conceptually interesting, as it solves the problem by finding a canonical form.; This approach can be generalized to other isomorphism problems.
**Cons:** Inefficient in both time and space due to expensive string manipulations (concatenation, comparison).; More complex to implement correctly compared to the direct recursive solution.
### Explanation
The core idea is to define a unique representation for any tree that is invariant under flip operations. We can achieve this with a recursive function, say `getCanonical(node)`, which returns a string.

For a given `node`, we first recursively get the canonical strings for its left and right children, let's call them `leftStr` and `rightStr`. If a child is `null`, we can represent it with a special marker like `"#"`. To ensure the representation is canonical, we order the child strings by comparing `leftStr` and `rightStr` lexicographically. The smaller string comes first. The final string for the `node` is formed by concatenating the node's value, the smaller child string, and the larger child string.

After generating the canonical strings for both `root1` and `root2`, we simply compare them for equality.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        String s1 = getCanonical(root1);
        String s2 = getCanonical(root2);
        return s1.equals(s2);
    }

    private String getCanonical(TreeNode node) {
        if (node == null) {
            return "#";
        }
        
        String left = getCanonical(node.left);
        String right = getCanonical(node.right);
        
        // To ensure canonical representation, order the children's strings lexicographically
        if (left.compareTo(right) > 0) {
            String temp = left;
            left = right;
            right = temp;
        }
        
        return String.valueOf(node.val) + "(" + left + ")(" + right + ")";
    }
}
```
### Algorithm
*   Implement a recursive function `getCanonical(TreeNode node)` that returns a canonical string representation of the subtree.
*   **Base Case:** If the input `node` is `null`, return a special marker string like `"#"`.
*   **Recursive Step:**
    *   Recursively call `getCanonical` on the left and right children to get their string representations, `leftStr` and `rightStr`.
    *   To ensure canonical ordering, compare `leftStr` and `rightStr` lexicographically. Swap them if `leftStr` is greater than `rightStr`.
    *   Construct and return the final string for the current node, for example: `node.val + "(" + leftStr + ")(" + rightStr + ")"`.
*   In the main `flipEquiv` function, generate the canonical strings for both `root1` and `root2`.
*   Return `true` if the two strings are equal, `false` otherwise.

## Direct Recursive Comparison
This is a direct and efficient approach that recursively checks for flip equivalence. The function compares two nodes and then explores two possibilities for their children: either they match directly (left with left, right with right) or they match after a flip (left with right, right with left).
**Time:** O(min(N1, N2)), where N1 and N2 are the number of nodes in the two trees. The function is called for each pair of nodes that could potentially match. In the worst case (when they are flip equivalent), we visit every node in the smaller tree once. · **Space:** O(min(H1, H2)), where H1 and H2 are the heights of the two trees. This space is used by the recursion stack. In the worst case of a skewed tree, this can be O(min(N1, N2)).
**Pros:** Highly efficient in terms of both time and space.; The logic directly follows the problem definition, making it intuitive and easy to implement.; Optimal solution for this problem.
**Cons:** There are no significant cons to this approach as it is optimal for this problem.
### Explanation
This method is based on the definition of flip equivalence. We define a recursive function that takes two nodes, one from each tree, and returns `true` if the subtrees rooted at these nodes are flip equivalent.

The function first handles the base cases: if both nodes are `null`, they are equivalent (`true`); if only one is `null` or their values differ, they are not equivalent (`false`).

If the base cases don't apply, it means we have two non-null nodes with the same value. We then proceed to the recursive step. There are two ways their children can match for the subtrees to be flip equivalent:
1.  **No Flip:** `root1.left` matches `root2.left` AND `root1.right` matches `root2.right`.
2.  **Flipped:** `root1.left` matches `root2.right` AND `root1.right` matches `root2.left`.

We recursively check both possibilities. If either one is true, the function returns `true`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        // Base case: both are null, they are equivalent
        if (root1 == null && root2 == null) {
            return true;
        }
        // Base case: one is null, or values don't match, they are not equivalent
        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        
        // Check for non-flipped equivalence
        boolean nonFlipped = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
        
        // Check for flipped equivalence
        boolean flipped = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
        
        // The trees are flip equivalent if either of the above conditions is true
        return nonFlipped || flipped;
    }
}
```
### Algorithm
*   Define a recursive function, let's call it `flipEquiv(node1, node2)`.
*   **Base Cases:**
    *   If both `node1` and `node2` are `null`, return `true`.
    *   If either `node1` or `node2` is `null`, or if `node1.val != node2.val`, return `false`.
*   **Recursive Step:**
    *   Recursively check the "no-flip" case: `flipEquiv(node1.left, node2.left)` AND `flipEquiv(node1.right, node2.right)`.
    *   Recursively check the "flipped" case: `flipEquiv(node1.left, node2.right)` AND `flipEquiv(node1.right, node2.left)`.
*   Return `true` if either the "no-flip" case OR the "flipped" case is true. Otherwise, return `false`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean flipEquiv ( TreeNode root1 , TreeNode root2 ) { return dfs ( root1 , root2 ); } private boolean dfs ( TreeNode root1 , TreeNode root2 ) { if ( root1 == root2 || ( root1 == null && root2 == null )) { return true ; } if ( root1 == null || root2 == null || root1 . val != root2 . val ) { return false ; } return ( dfs ( root1 . left , root2 . left ) && dfs ( root1 . right , root2 . right )) || ( dfs ( root1 . left , root2 . right ) && dfs ( root1 . right , root2 . left )); } }
```

### JavaScript

```javascript
function flipEquiv ( root1 , root2 ) { if ( root1 === root2 ) return true ; if ( ! root1 || ! root2 || root1 ?. val !== root2 ?. val ) return false ; const { left : l1 , right : r1 } = root1 ; const { left : l2 , right : r2 } = root2 ; return ( flipEquiv ( l1 , l2 ) && flipEquiv ( r1 , r2 )) || ( flipEquiv ( l1 , r2 ) && flipEquiv ( r1 , l2 )); }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool flipEquiv ( TreeNode * root1 , TreeNode * root2 ) { return dfs ( root1 , root2 ); } bool dfs ( TreeNode * root1 , TreeNode * root2 ) { if ( root1 == root2 || ( ! root1 && ! root2 )) return true ; if ( ! root1 || ! root2 || root1 -> val != root2 -> val ) return false ; return ( dfs ( root1 -> left , root2 -> left ) && dfs ( root1 -> right , root2 -> right )) || ( dfs ( root1 -> left , root2 -> right ) && dfs ( root1 -> right , root2 -> left )); } };
```

### Python

```python
# 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 class Solution : def flipEquiv ( self , root1 : Optional [ TreeNode ], root2 : Optional [ TreeNode ]) -> bool : def dfs ( root1 , root2 ): if root1 == root2 or ( root1 is None and root2 is None ): return True if root1 is None or root2 is None or root1 . val != root2 . val : return False return ( dfs ( root1 . left , root2 . left ) and dfs ( root1 . right , root2 . right )) or ( dfs ( root1 . left , root2 . right ) and dfs ( root1 . right , root2 . left ) ) return dfs ( root1 , root2 )
```