Flip Equivalent Binary Trees
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
A flip on a binary tree picks one node and swaps its left and right child subtrees.
Two trees are flip equivalent when some number of flips (possibly none) turns the first into the second.
Given the roots root1 and root2, return True if the two trees are flip equivalent and False otherwise. All values within each tree are unique.
Examples
Input: root1 = [1,2,3,4,5], root2 = [1,3,2,null,null,5,4] Output: True
Flip the root, which puts 3 on the left, then flip node 2, which puts 5 before 4.
Input: root1 = [1,2,3], root2 = [1,2,4] Output: False
The trees hold different values, so no flips can make them equal.
Input: root1 = [], root2 = [] Output: True
Two empty trees are equal with no flips.
Constraints
- 0 <= number of nodes in each tree <= 100
- 0 <= Node.val <= 99
- Values are unique within each tree
Approaches
- Baseline: canonical strings with children sorted — time O(n²) worst case for the string building, space O(n²) worst case
Follow-up
What if values may repeat? Then both pairings can look plausible at a node, and trying both naively can blow up. A canonical form (the baseline here) or the shape ids of the use case “Same shape under flips, values ignored” keep it polynomial. And if you must say how many flips are needed, see “Fewest flips to match”.
Related problems
Start free on Cariara · Coding problems · System design studio
