Flip Equivalent Binary Trees

Problem Statement

In this scenario, we are dealing with binary trees and a specific operation known as a "flip operation." A flip involves choosing any node within a binary tree and swapping its left and right child subtrees. The primary challenge is to determine whether two given binary trees, denoted as X and Y, can be rendered identical through a series of these operations. The trees are considered flip equivalent if it's possible to transform tree X into tree Y using any number of flips. The function should return true if the trees are flip equivalent and false otherwise, based on the roots root1 and root2 of these binary trees.

Examples

Example 1

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].

Approach and Intuition

To tackle the problem of determining whether two trees are flip equivalent, observe the nature of the flip operation and utilize a recursive strategy.

1. Begin by examining the simplest case: if both trees are empty (i.e., the roots root1 and root2 are null). In this scenario, the trees are trivially flip equivalent, and we should return true.

2. Next, consider the case where one tree is empty, and the other is not. This situation directly leads to a false result, as an empty tree cannot be made equivalent to a non-empty tree through any number of flips.

3. For trees that are not empty, compare the root values of root1 and root2. If these values differ, return false immediately as differing root values cannot be reconciled through subtree flips.

4. If the roots are the same, recursively check two potential scenarios due to the flip's nature:

   • The left child of root1 might become equivalent to either the left child of root2 or its right child (and similarly for the right child). Thus, check the flip equivalency by recursively assessing:

     • (root1.left, root2.left) and (root1.right, root2.right) for regular child alignment.
     • (root1.left, root2.right) and (root1.right, root2.left) for flipped child alignment.

5. The trees are flip equivalent if either of the recursive conditions stated above holds true for subtree checks.

By following this recursive approach, each node and its respective children are compared against the potential flip equivalents. The use of recursion leverages the inherently nested structure of the subtree swappings, making the solution both intuitive and efficient within the given constraints.

Solutions

class Solution {
public:
    void toCanonical(TreeNode* node) {
        if (!node) return;
    
        toCanonical(node->left);
        toCanonical(node->right);
    
        if (!node->right) return;
        if (!node->left) {
            node->left = node->right;
            node->right = NULL;
            return;
        }
    
        TreeNode* lChild = node->left;
        TreeNode* rChild = node->right;
        if (lChild->val > rChild->val) {
            node->left = rChild;
            node->right = lChild;
        }
    }
    
    bool checkEquivalent(TreeNode* n1, TreeNode* n2) {
        if (!n1 && !n2) return true;
        if (!n1 || !n2) return false;
        if (n1->val != n2->val) return false;
    
        return checkEquivalent(n1->left, n2->left) &&
               checkEquivalent(n1->right, n2->right);
    }
    
    bool flipEquivalent(TreeNode* n1, TreeNode* n2) {
        toCanonical(n1);
        toCanonical(n2);
        return checkEquivalent(n1, n2);
    }
};