Flip Equivalent Binary Trees — Problem & Solution
Flip Equivalent Binary Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Flip Equivalent Binary Trees is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A flip on a binary tree chooses one node and swaps its left and right subtrees.
Two trees are flip equivalent if some sequence of flips (possibly none) turns the first into the second. Given the roots root1 and root2 of two binary trees, each with distinct values, return true if they 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
Explanation: Flip the children of 1, of 3 and of 5 in the first tree and you get the second.
Example 2
Input: root1 = [1,2,3,4], root2 = [1,3,2,4]
Output: false
Explanation: In the first tree 4 hangs under 2, in the second under 3. Flips only swap a node's two children, so they can never move 4 to another parent.
Example 3
Input: root1 = [], root2 = []
Output: true
Explanation: Two empty trees are equivalent without any flip.
Constraints
The number of nodes in each tree is in the range [0, 100]Each tree has unique node values in the range [0, 99]
Hints for Flip Equivalent Binary Trees
Hint 1
Flips never change which node is whose parent — only the left/right order. So the roots must match first.
Hint 2
Then the pair of children must match as a pair: either left with left and right with right, or left with right and right with left.
Hint 3
Recurse:
equiv(a, b)is true when both are null, false when exactly one is null or the values differ, and otherwise one of the two pairings must be equivalent on both sides.
How to solve Flip Equivalent Binary Trees
A flip only reorders a node's two children, so two trees are flip equivalent exactly when their roots agree and their children can be paired up — straight or crossed — into flip-equivalent subtrees. That is a direct recursion.
Approach
- If both nodes are null, return true; if only one is null, return false.
- If their values differ, return false.
- Return
(equiv(a.left, b.left) && equiv(a.right, b.right)) || (equiv(a.left, b.right) && equiv(a.right, b.left)).
Why it works
Any sequence of flips can be reordered so that the flip at the root (if any) is decided first and the rest act independently inside the two subtrees; so the trees match exactly when one of the two pairings matches recursively. With distinct values, at most one pairing can have matching child roots, so the recursion does constant work per node.
Complexity
- Time —
O(min(n1, n2)) with distinct values - Space —
O(h) for the recursion
Pitfalls
- Compare values before recursing; otherwise the two-way branching can explode.
- Two empty trees are equivalent; an empty and a non-empty tree are not.
- Matching the multiset of values is not enough — the parent of every node must agree.
Reference solution
Python
from typing import Optional
def flipEquiv(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if root1 is None or root2 is None:
return root1 is root2
if root1.val != root2.val:
return False
return (flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)) or \
(flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left))Java
public static boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) return root1 == root2;
if (root1.val != root2.val) return false;
return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right))
|| (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
}C++
bool flipEquiv(TreeNode* root1, TreeNode* root2) {
if (!root1 || !root2) return root1 == root2;
if (root1->val != root2->val) return false;
return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right))
|| (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
}JavaScript
var flipEquiv = function(root1, root2) {
if (root1 === null || root2 === null) return root1 === root2;
if (root1.val !== root2.val) return false;
return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
(flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals