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.

Examples

Example 1:

1
2
3

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:

1
2

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

Example 3:

1
2

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

Solution

Method 1 - Recursive DFS

To determine if two binary trees are flip equivalent, we need to recursively check the following conditions for corresponding subtrees:

  1. Both roots should be null, or both should have the same value. (This can be written more concisely as - If at least one of the two root nodes is null, are they equal? if yes, true; if no, false;)
  2. otherwise, neither node is null; if the values of the two nodes are:
  3. Recursively check if their children are equivalent. This can occur in two situations:
    • No flip: The left child of root1 is equivalent to the left child of root2 and the right child of root1 is equivalent to the right child of root2.
    • Flip: The left child of root1 is equivalent to the right child of root2 and the right child of root1 is equivalent to the left child of root2.

Basically, if both the trees match exactly recursively, we can still flip them. If they are mirror of each other, they are still equal, because that is waht we want to do.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        // If both nodes are null, they are flip equivalent
        if (root1 == null && root2 == null) {
	        return true;
	    }
        
        // If one is null or their values are not equal, they are not flip equivalent
        if (root1 == null || root2 == null || root1.val != root2.val) {
	        return false;
	    }
        
        // Perform the recursive checks
        // Check if they are flip equivalent without a flip
        boolean noFlip = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
        
        // Check if they are flip equivalent with a flip
        boolean flip = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
        
        // Return true if either scenario holds
        return noFlip || flip;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	public boolean flipEquiv(TreeNode root1, TreeNode root2) {
		if (root1 == null || root1 == null) {
			return root1 == root1;
		}
		return root1.val == root2.val &&
			   (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) || 
			   flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        # If both nodes are null, they are flip equivalent
        if root1 is None and root2 is None:
            return True
        
        # If one is null or their values are not equal, they are not flip equivalent
        if root1 is None or root2 is None or root1.val != root2.val:
            return False
        
        # Perform the recursive checks
        # Check if they are flip equivalent without a flip
        no_flip = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
        
        # Check if they are flip equivalent with a flip
        flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)
        
        # Return true if either scenario holds
        return no_flip or flip

Complexity

  • ⏰ Time complexity: O(min(n1, n2)), where n1 and n2 are the number of nodes in trees root1 and root2, respectively. Each node is visited once.
  • 🧺 Space complexity: O(min(h1, h2)), where h1 and h2 are the heights of trees root1 and root2, respectively. This is due to the recursion stack.

Method 2 - Iterative BFS

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        Queue<TreeNode> q1 = new LinkedList<>(), q2 = new LinkedList<>();
        q1.offer(root1);
        q2.offer(root2);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode n1 = q1.poll(), n2 = q2.poll();
            if (n1 == null || n2 == null) {
                if (n1 != n2) {
	                return false;
	            }
                else continue;
            }
            if (n1.val != n2.val) {
                return false;
            }
            if (n1.left == n2.left || n1.left != null && n2.left != null && n1.left.val == n2.left.val) {
                q1.addAll(Arrays.asList(n1.left, n1.right));
            }else {
                q1.addAll(Arrays.asList(n1.right, n1.left));
            }
            q2.addAll(Arrays.asList(n2.left, n2.right));
        }
        return q1.isEmpty() && q2.isEmpty();
    }
}