MediumTreeDepth-First SearchBinary Tree

Flip Equivalent Binary Trees

1 approach, code in every language

A flip operation on a binary tree chooses any node and swaps its left and right subtrees. Two binary trees are flip equivalent if one can be transformed into the other by performing some sequence of these flips (possibly none).

Given the roots root1 and root2 of two binary trees, return true if the trees are flip equivalent and false otherwise.

Example 1

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

Flipping the subtree rooted at node 1's children, and then a nested flip lower down, turns the first tree into the second while keeping every value in place.

Example 2

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

Output: false

An empty tree can never be made equal to a tree that contains a node, since flips never add or remove values.

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

Recursive Match-or-Flip

At each node, accept the children either aligned as-is or after a single flip.

Loading animation…

Intuition

Flip equivalence is decided top-down: two trees can be aligned only if their roots hold the same value, and then their subtrees can be paired up in one of two ways. Either the left of one matches the left of the other and the rights match too, or a flip is applied so that left matches right and right matches left. Because node values are unique within a tree, we never have to worry about ambiguous pairings, and a greedy either/or check at each node is sufficient. The recursion bottoms out when both nodes are null (equivalent) or when exactly one is null or values differ (not equivalent). Each pair of nodes is compared once, so the algorithm runs in time proportional to the tree size.

Algorithm walkthrough

1If both nodes are null, the (empty) subtrees are flip equivalent, return true.
2If exactly one node is null, or the two values differ, return false.
3Compute the no-flip case: left children match and right children match.
4Compute the flip case: root1's left matches root2's right and root1's right matches root2's left.
5Return true if either the no-flip case or the flip case holds.
6The top-level call returns the answer for the whole trees.

Implementation

class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None and root2 is None:
            return True
        if root1 is None or root2 is None or root1.val != root2.val:
            return False
        no_flip = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
        flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)
        return no_flip or flip

Time

O(min(n1, n2))

Space

O(min(h1, h2))

Recursion stops as soon as either tree runs out of nodes, so the number of matched pairs is bounded by the smaller tree. The stack depth is bounded by the smaller tree's height.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free