We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flip Equivalent Binary Trees

Number: 988

Difficulty: Medium

Paid? No

Companies: Google, Anduril, Amazon, Microsoft

Problem Description

Given the roots of two binary trees, determine if they are flip equivalent. Two trees are flip equivalent if one can be transformed into the other by swapping the left and right children of some nodes any number of times.

Key Insights

  • Use recursion (DFS) to compare nodes from both trees.
  • Two trees are flip equivalent if:
    • Both nodes are null: they are equivalent.
    • Only one is null: they are not equivalent.
    • If the node values are the same and either:
      • The children are equivalent without a flip, or
      • The children are equivalent with a flip.
  • The recursive check has to verify both the flipped and non-flipped scenarios.

Space and Time Complexity

Time Complexity: O(min(n1, n2)) where n1 and n2 are the number of nodes in the two trees. In worst-case, it can visit every node. Space Complexity: O(H) where H is the height of the tree due to the recursion stack.

Solution

We use a recursive depth-first search approach. At each node, we check the following:

  1. If both nodes are null, they are equivalent.
  2. If one node is null or the values differ, they are not equivalent.
  3. Otherwise, we recursively check two scenarios:
    • Without flipping: compare left with left and right with right.
    • With flipping: compare left with right and right with left. If either scenario holds true, the current pair of nodes are considered flip equivalent. Data structures used are the tree nodes themselves and the recursion call stack for DFS.

Code Solutions

# 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

def flipEquiv(root1: TreeNode, root2: TreeNode) -> bool:
    # If both nodes are None, they are equivalent.
    if not root1 and not root2:
        return True
    # If one is None or values differ, trees are not equivalent.
    if not root1 or not root2 or root1.val != root2.val:
        return False
    # Check both non-flipped and flipped scenarios recursively.
    return (flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)) or \
           (flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left))

# Example usage:
# Construct trees and call flipEquiv(root1, root2)
← Back to All Questions