Flip Equivalent Binary Trees

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

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean flipEquiv(TreeNode root1, TreeNode root2) {18        String s1 = getCanonical(root1);19        String s2 = getCanonical(root2);20        return s1.equals(s2);21    }22 23    private String getCanonical(TreeNode node) {24        if (node == null) {25            return "#";26        }27        28        String left = getCanonical(node.left);29        String right = getCanonical(node.right);30        31        // To ensure canonical representation, order the children's strings lexicographically32        if (left.compareTo(right) > 0) {33            String temp = left;34            left = right;35            right = temp;36        }37        38        return String.valueOf(node.val) + "(" + left + ")(" + right + ")";39    }40}

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

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean flipEquiv(TreeNode root1, TreeNode root2) {18        // Base case: both are null, they are equivalent19        if (root1 == null && root2 == null) {20            return true;21        }22        // Base case: one is null, or values don't match, they are not equivalent23        if (root1 == null || root2 == null || root1.val != root2.val) {24            return false;25        }26        27        // Check for non-flipped equivalence28        boolean nonFlipped = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);29        30        // Check for flipped equivalence31        boolean flipped = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);32        33        // The trees are flip equivalent if either of the above conditions is true34        return nonFlipped || flipped;35    }36}