Domain 2MediumMEDIUM

Flip Equivalent Binary Trees

LeetCode problem 951: Flip Equivalent Binary Trees (medium).

Domain: medium•Updated: 2026-09-04
#Tree

Problem Breakdown

We are given two binary trees rooted at root1 and root2. A “flip” operation allows us to swap the left and right children of any node. Two trees are considered Flip Equivalent if we can transform one into the other using zero or more flip operations.

  • Inputs: Two tree roots (root1, root2).
  • Output: Boolean indicating equivalence.
  • Constraints: Node values are unique (0-99), node counts up to 100. Trees can be empty.
  • Edge Cases:
    • Both trees empty -> Equivalent.
    • One tree empty, one not -> Not equivalent.
    • Same structure but different left/right children order at a specific level (requires flip).

Intuition

A brute-force approach would involve trying every possible combination of flips for the subtrees to see if they match. Since there are 2N2^N potential configurations where NN is the number of nodes, this exponential complexity (O(2depth)O(2^{depth})) is infeasible.

The key insight is that equivalence must hold recursively from the root down:

  1. The roots must have identical values (since flips don’t change node values).
  2. If we assume no flip occurred at the current node, root1.left must match root2.left, and root1.right must match root2.right.
  3. However, if a flip did occur at this specific node (or an ancestor), then root1.left might actually correspond to root2.right, and vice versa.

Therefore, for any two nodes with the same value, we check both possibilities: matching children directly OR swapping them before checking recursively. If either path leads to a full match down the tree, they are equivalent.

Approach

We use Depth-First Search (DFS) recursion starting from the roots of root1 and root2.

  1. Base Case:
    • If both nodes are None, return True (empty trees match).
    • If only one node is None, or their values differ, return False.
  2. Recursive Step:
    • Check if the subtrees match without flipping: dfs(root1.left, root2.left) AND dfs(root1.right, root2.right).
    • Check if they match with a flip at this node: dfs(root1.left, root2.right) AND dfs(root1.right, root2.left).
  3. Result: Return the logical OR of these two checks.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes in the tree (specifically min⁡(nodes(root1),nodes(root2))\min(\text{nodes}(root1), \text{nodes}(root2))). We visit each node exactly once because we prune branches that fail value checks immediately. In the worst case, every node must be visited to confirm equivalence or non-equivalence.
  • Space Complexity: O(H)O(H) where HH is the height of the tree due to recursion stack usage. This ranges from O(log⁡N)O(\log N) for balanced trees to O(N)O(N) for skewed trees (linked list structure).

Solution

# 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

class Solution:
    def flipEquivalent(self, root1: 'TreeNode', root2: 'TreeNode') -> bool:
        # Base case: Both nodes are None (empty subtrees match)
        if not root1 and not root2:
            return True
        
        # If one is None or values differ, they cannot be equivalent
        if not root1 or not root2 or root1.val != root2.val:
            return False
            
        # Check two possibilities: 
        # 1. No flip at current node (Left matches Left, Right matches Right)
        # 2. Flip occurred at current node (Left matches Right, Right matches Left)
        no_flip = self.flipEquivalent(root1.left, root2.left) and \
                  self.flipEquivalent(root1.right, root2.right)
                  
        flip_occurred = self.flipEquivalent(root1.left, root2.right) and \
                        self.flipEquivalent(root1.right, root2.left)
                        
        return no_flip or flip_occurred

Edge Cases Handled

  • Empty Trees: The if not root1 and not root2 condition returns True, correctly handling two empty trees.
  • Mismatched Sizes/Structure: If one tree is exhausted (None) while the other has nodes, it hits not root1 or not root2, returning False.
  • Value Mismatch: The check root1.val != root2.val ensures structural equivalence only happens if node values align.
  • Flip Requirement: By checking both direct and swapped child recursions (no_flip OR flip_occurred), we account for the specific operation allowed by the problem statement without modifying the tree structure in place (which would be O(N)O(N) space/time overhead to revert).