Flip Equivalent Binary Trees - Solution & Explanation
Problem Statement
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or 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: We flipped at nodes with values 1, 3, and 5.
Example 2:
Input: root1 = [], root2 = [] Output: true
Example 3:
Input: root1 = [], root2 = [1] Output: false
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].
Approach Overview
Problem Overview: Two binary trees are flip equivalent if you can make them identical by repeatedly swapping the left and right children of any node. The task is to determine whether two given trees can become the same after any number of flips.
Approach 1: Recursive DFS Comparison (O(n) time, O(h) space)
The most natural solution uses recursion with Depth-First Search. Start from the root of both trees and compare nodes. If values differ, the trees cannot be equivalent. Otherwise, recursively check two possible configurations: (1) left with left and right with right, or (2) left with right and right with left. If either configuration returns true, the current nodes are flip equivalent. The recursion continues until all nodes match or a mismatch is found. Each node is visited once, giving O(n) time, while recursion depth depends on tree height O(h).
This approach works because flips only affect the order of children, not node values or subtree structure. By evaluating both possible pairings at every node, you effectively simulate every valid flip configuration without actually modifying the tree.
Approach 2: Iterative DFS Using Stack (O(n) time, O(n) space)
An iterative alternative uses an explicit stack instead of recursion. Push the root pair onto the stack and process nodes in DFS order. For each pair, compare values and determine whether children match directly or require a flip. Based on the match condition, push the correct child pairs onto the stack. This avoids recursion depth limits and gives more control over traversal. Time complexity remains O(n) since each node pair is processed once, while the stack may store up to O(n) nodes in skewed trees.
This method is useful in environments where recursion depth could overflow, especially with very deep tree structures.
Recommended for interviews: The recursive DFS solution is the expected answer. It is concise, directly models the flip logic, and clearly demonstrates understanding of binary tree traversal and subtree comparison. Interviewers usually look for the insight that two configurations must be checked at every node. The iterative stack version is a good follow‑up showing you can convert recursion into an explicit DFS implementation.
Approach 1: Recursive Approach
This approach uses a recursive function to check if both trees are identical or one is a flipped version of the other. For each pair of nodes, we check if subtree structures match directly or with a flip.
In this C implementation, a recursive function flipEquiv is called for each node. It first checks base cases, including if both nodes are null (return true), or if one is null and the other isn't (return false). Then it checks if the current nodes are equal in value and recursively checks for their children in both non-flipped and flipped scenarios.
Complexity
Time Complexity: O(N), where N is the total number of nodes, since we visit each node once.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
Approach 2: Iterative Approach Using Stack
In this approach, instead of recursion, we use a stack for depth-first search. It proceeds similarly by evaluating if nodes are flip equivalent, but uses an explicit stack rather than the call stack.
In this Python implementation, we use a stack to iteratively check node pairs. We continue popping nodes to compare for equivalency in both standard and flipped orientations until the stack is empty.
Code
Python
JavaScript
Complexity
Time Complexity: O(N).
Space Complexity: O(H), similar to the recursive approach.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(N), where N is the total number of nodes, since we visit each node once. |
| Iterative Approach Using Stack | Time Complexity: O(N). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS Comparison | O(n) | O(h) | Best general solution. Clean logic and preferred in interviews. |
| Iterative DFS Using Stack | O(n) | O(n) | Useful when avoiding recursion or handling very deep trees. |
Video Solution
Flip Equivalent Binary Trees - Leetcode 951 - Python • NeetCode • 17,745 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Flip Equivalent Binary Trees easy or hard?
Flip Equivalent Binary Trees Python/Java solution
How to solve Flip Equivalent Binary Trees in O(n)?
What is the best approach for Flip Equivalent Binary Trees?
Is Flip Equivalent Binary Trees asked at Google/Amazon/Meta?
What data structure is used in Flip Equivalent Binary Trees?
What is the time complexity of Flip Equivalent Binary Trees?
Ready to solve this problem?
Practice Flip Equivalent Binary Trees with our built-in code editor and test cases.
Practice on FleetCode