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:
[0, 100].[0, 99].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.
C++
Java
Python
C#
JavaScript
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.
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.
JavaScript
Time Complexity: O(N).
Space Complexity: O(H), similar to the recursive approach.
| 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). |
Invert Binary Tree - Depth First Search - Leetcode 226 • NeetCode • 287,306 views views
Watch 9 more video solutions →Practice Flip Equivalent Binary Trees with our built-in code editor and test cases.
Practice on FleetCode