# LeetCode 951: Flip Equivalent Binary Trees

## Problem Restatement

We are given the roots of two binary trees, `root1` and `root2`.

A flip operation chooses one node and swaps its left and right child subtrees.

Two trees are flip equivalent if we can make them equal after doing zero or more flip operations.

Return `true` if the two trees are flip equivalent. Otherwise, return `false`.

The official constraints say each tree has between `0` and `100` nodes, and each tree has unique node values in the range `[0, 99]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root1`, the root of the first binary tree |
| Input | `root2`, the root of the second binary tree |
| Output | `true` if the trees are flip equivalent, otherwise `false` |
| Operation | At any node, swap its left and right child subtrees |

Example function shape:

```python
def flipEquiv(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    ...
```

## Examples

Example 1:

```python
root1 = [1,2,3,4,5,6,None,None,None,7,8]
root2 = [1,3,2,None,6,4,5,None,None,None,None,8,7]
```

Output:

```python
True
```

These trees can be made equal by flipping some nodes. The LeetCode example says the flips happen at nodes with values `1`, `3`, and `5`.

Example 2:

```python
root1 = []
root2 = []
```

Output:

```python
True
```

Two empty trees are equivalent.

Example 3:

```python
root1 = []
root2 = [1]
```

Output:

```python
False
```

One tree is empty and the other is not, so they cannot be equivalent.

## First Thought: Direct Tree Comparison

If flips were not allowed, this would be the same as checking whether two trees are identical.

For each pair of nodes, we would check:

```python
root1.val == root2.val
```

Then we would compare:

```python
root1.left  with root2.left
root1.right with root2.right
```

But this is not enough here.

Because flips are allowed, the left child of one tree may match the right child of the other tree.

So at each pair of nodes, there are two valid possibilities.

## Key Insight

For two nodes to be flip equivalent, three things must hold.

First, both nodes must exist, or both must be `None`.

Second, if both nodes exist, their values must be equal.

Third, their children must match in one of two ways:

```python
# No flip
root1.left  matches root2.left
root1.right matches root2.right
```

or:

```python
# Flip
root1.left  matches root2.right
root1.right matches root2.left
```

This gives a natural recursive solution.

At every node, we recursively check both child arrangements. If either arrangement works, the current subtree pair is flip equivalent.

## Algorithm

Use DFS recursion.

For every pair of nodes `a` and `b`:

1. If both are `None`, return `True`.
2. If only one is `None`, return `False`.
3. If `a.val != b.val`, return `False`.
4. Check the no-flip case.
5. Check the flip case.
6. Return `True` if either case works.

The recursive condition is:

```python
same = dfs(a.left, b.left) and dfs(a.right, b.right)
flipped = dfs(a.left, b.right) and dfs(a.right, b.left)

return same or flipped
```

## Correctness

We prove that the algorithm returns `True` exactly when the two trees are flip equivalent.

If both current nodes are `None`, the two empty subtrees are equal, so returning `True` is correct.

If exactly one current node is `None`, then one subtree has a node where the other has no node. No flip can create or remove nodes, so returning `False` is correct.

If both nodes exist but their values differ, no flip can change node values. Therefore, the two subtrees cannot become equal, so returning `False` is correct.

Now assume both nodes exist and have the same value. A flip at this node has only two possible outcomes. Either the children stay aligned directly, or the children are swapped. The algorithm checks both possibilities:

```python
dfs(a.left, b.left) and dfs(a.right, b.right)
```

and:

```python
dfs(a.left, b.right) and dfs(a.right, b.left)
```

If either condition is true, then the child subtrees can be made equal under the corresponding arrangement, so the current subtrees are flip equivalent.

If both conditions are false, then neither possible child arrangement can make the subtrees equal. Since a flip only swaps the two children, there is no third arrangement to try. Therefore, the current subtrees are not flip equivalent.

By applying this reasoning recursively to every pair of compared subtrees, the algorithm correctly decides whether the two whole trees are flip equivalent.

## Complexity

Let `n` be the number of nodes in the trees.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each matching node pair is processed with constant work |
| Space | `O(h)` | The recursion stack uses one frame per tree level |

Here, `h` is the height of the tree.

In the worst case, a skewed tree has height `n`, so the space complexity can be `O(n)`.

For a balanced tree, the recursion depth is `O(log n)`.

## Implementation

```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

from typing import Optional

class Solution:
    def flipEquiv(
        self,
        root1: Optional[TreeNode],
        root2: Optional[TreeNode],
    ) -> bool:
        if root1 is None and root2 is None:
            return True

        if root1 is None or root2 is None:
            return False

        if root1.val != root2.val:
            return False

        same = (
            self.flipEquiv(root1.left, root2.left)
            and self.flipEquiv(root1.right, root2.right)
        )

        flipped = (
            self.flipEquiv(root1.left, root2.right)
            and self.flipEquiv(root1.right, root2.left)
        )

        return same or flipped
```

## Code Explanation

The first base case handles two empty subtrees:

```python
if root1 is None and root2 is None:
    return True
```

Two empty subtrees are already equal.

The second base case handles shape mismatch:

```python
if root1 is None or root2 is None:
    return False
```

If only one node exists, the subtrees cannot match.

Then we compare values:

```python
if root1.val != root2.val:
    return False
```

A flip changes child positions only. It does not change values.

After that, we try the direct child pairing:

```python
same = (
    self.flipEquiv(root1.left, root2.left)
    and self.flipEquiv(root1.right, root2.right)
)
```

This means no flip is needed at the current node.

Then we try the swapped child pairing:

```python
flipped = (
    self.flipEquiv(root1.left, root2.right)
    and self.flipEquiv(root1.right, root2.left)
)
```

This means a flip is allowed at the current node.

Finally:

```python
return same or flipped
```

The current subtrees are flip equivalent if either arrangement works.

## Testing

For local testing, we can build trees from level-order arrays.

```python
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    queue = deque([root])
    i = 1

    while queue and i < len(values):
        node = queue.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1

    return root

def run_tests():
    s = Solution()

    root1 = build_tree([1, 2, 3, 4, 5, 6, None, None, None, 7, 8])
    root2 = build_tree([1, 3, 2, None, 6, 4, 5, None, None, None, None, 8, 7])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([])
    root2 = build_tree([])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([])
    root2 = build_tree([1])
    assert s.flipEquiv(root1, root2) is False

    root1 = build_tree([1, 2, 3])
    root2 = build_tree([1, 3, 2])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([1, 2, None])
    root2 = build_tree([1, None, 2])
    assert s.flipEquiv(root1, root2) is True

    root1 = build_tree([1, 2, 3])
    root2 = build_tree([1, 2, 4])
    assert s.flipEquiv(root1, root2) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Large official-style example | Checks flips at multiple levels |
| Two empty trees | Checks base case |
| One empty tree | Checks shape mismatch |
| `[1,2,3]` vs `[1,3,2]` | Checks flip at root |
| Single child on opposite sides | Checks one-sided subtree flip |
| Different values | Checks value mismatch |