Flip Equivalent Binary Trees

medium binary tree dfs recursion

Problem

A flip operation on a binary tree swaps the left and right children of any node. Two binary trees are flip equivalent if and only if one can be turned into the other after some number of flip operations. Given the roots of two binary trees root1 and root2, return true if the trees are flip equivalent.

Inputroot1 = [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]

Outputtrue

Flipping the children at node 1 and at node 5 turns the first tree into the second.

root1 (level-order, use null for gaps)

root2 (level-order, use null for gaps)

def flip_equiv(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None or a.val != b.val:
        return False
    return (flip_equiv(a.left, b.left) and flip_equiv(a.right, b.right)) or \
           (flip_equiv(a.left, b.right) and flip_equiv(a.right, b.left))

function flipEquiv(a, b) {
  if (a === null && b === null) return true;
  if (a === null || b === null || a.val !== b.val) return false;
  return (flipEquiv(a.left, b.left) && flipEquiv(a.right, b.right)) ||
         (flipEquiv(a.left, b.right) && flipEquiv(a.right, b.left));
}

class Solution {
    public boolean flipEquiv(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null || a.val != b.val) return false;
        return (flipEquiv(a.left, b.left) && flipEquiv(a.right, b.right))
            || (flipEquiv(a.left, b.right) && flipEquiv(a.right, b.left));
    }
}

bool flipEquiv(TreeNode* a, TreeNode* b) {
    if (a == nullptr && b == nullptr) return true;
    if (a == nullptr || b == nullptr || a->val != b->val) return false;
    return (flipEquiv(a->left, b->left) && flipEquiv(a->right, b->right))
        || (flipEquiv(a->left, b->right) && flipEquiv(a->right, b->left));
}

Explanation

Two trees are flip equivalent if we can match them by optionally swapping the children at any node. The solution compares them recursively, trying both the unswapped and the swapped pairing at every node.

First the base cases: if both nodes are null, they match. If only one is null, or their values differ, this pair can never match no matter how we flip below them, so we return false.

When the two values agree, there are exactly two ways the subtrees could line up. Either left matches left and right matches right (no flip), or left matches right and right matches left (a flip). We return true if either option works, joined by an or.

Example: root1 = [1,2,3,4,5] vs root2 = [1,3,2,null,null,5,4]. At the root both are 1; the no-flip pairing fails because 2 ≠ 3, but the flipped pairing matches 2 with 2 and 3 with 3, and the leaves line up, so the answer is true.

Each node pair is examined once, so this is O(n) time with recursion depth equal to the tree height.

Time: O(n) Space: O(h)