{x}
blog image

Flip Equivalent Binary Trees

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

Solution Explanation:

This problem asks whether two binary trees are flip equivalent. Two binary trees are flip equivalent if one can be made equal to the other through a series of left-right child swaps at any node. The solution uses Depth-First Search (DFS) to recursively compare the trees.

Approach:

The core idea is a recursive depth-first search (dfs). The dfs function compares two tree nodes:

  1. Base Cases:

    • If both nodes are null or identical, they are flip equivalent (return true).
    • If one node is null and the other isn't, or if the values of the nodes don't match, they are not flip equivalent (return false).

  2. Recursive Step:

    • If the values match, the function checks two possibilities:

      • The left subtree of root1 is equivalent to the left subtree of root2, AND the right subtree of root1 is equivalent to the right subtree of root2. This is a direct comparison.
      • OR the left subtree of root1 is equivalent to the right subtree of root2, AND the right subtree of root1 is equivalent to the left subtree of root2. This accounts for the flip operation.

    • The function recursively calls dfs for each comparison. If either condition is true, the nodes are flip equivalent (return true); otherwise, they're not (return false).

Time and Space Complexity Analysis:

  • Time Complexity: O(min(N1, N2)), where N1 and N2 are the number of nodes in root1 and root2 respectively. In the worst case, the algorithm visits each node once in both trees if they are flip equivalent or until it finds a mismatch.

  • Space Complexity: O(min(H1, H2)), where H1 and H2 are the heights of root1 and root2 respectively. This is due to the recursive call stack. In the worst-case scenario (perfectly balanced trees), the height is logarithmic to the number of nodes.

Code Explanation (Python):

The Python code directly implements the described recursive approach.

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)

The other language implementations follow the same logic, adapting syntax and data structures to their respective languages. For example, the Java code uses TreeNode objects and Java's syntax for recursion. The differences are mainly stylistic; the core algorithm remains the same.