Problem Breakdown
We are given two binary trees rooted at root1 and root2. A “flip” operation allows us to swap the left and right children of any node. Two trees are considered Flip Equivalent if we can transform one into the other using zero or more flip operations.
- Inputs: Two tree roots (
root1,root2). - Output: Boolean indicating equivalence.
- Constraints: Node values are unique (0-99), node counts up to 100. Trees can be empty.
- Edge Cases:
- Both trees empty -> Equivalent.
- One tree empty, one not -> Not equivalent.
- Same structure but different left/right children order at a specific level (requires flip).
Intuition
A brute-force approach would involve trying every possible combination of flips for the subtrees to see if they match. Since there are potential configurations where is the number of nodes, this exponential complexity () is infeasible.
The key insight is that equivalence must hold recursively from the root down:
- The roots must have identical values (since flips don’t change node values).
- If we assume no flip occurred at the current node,
root1.leftmust matchroot2.left, androot1.rightmust matchroot2.right. - However, if a flip did occur at this specific node (or an ancestor), then
root1.leftmight actually correspond toroot2.right, and vice versa.
Therefore, for any two nodes with the same value, we check both possibilities: matching children directly OR swapping them before checking recursively. If either path leads to a full match down the tree, they are equivalent.
Approach
We use Depth-First Search (DFS) recursion starting from the roots of root1 and root2.
- Base Case:
- If both nodes are
None, returnTrue(empty trees match). - If only one node is
None, or their values differ, returnFalse.
- If both nodes are
- Recursive Step:
- Check if the subtrees match without flipping:
dfs(root1.left, root2.left)ANDdfs(root1.right, root2.right). - Check if they match with a flip at this node:
dfs(root1.left, root2.right)ANDdfs(root1.right, root2.left).
- Check if the subtrees match without flipping:
- Result: Return the logical OR of these two checks.
Complexity Analysis
- Time Complexity: where is the number of nodes in the tree (specifically ). We visit each node exactly once because we prune branches that fail value checks immediately. In the worst case, every node must be visited to confirm equivalence or non-equivalence.
- Space Complexity: where is the height of the tree due to recursion stack usage. This ranges from for balanced trees to for skewed trees (linked list structure).
Solution
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flipEquivalent(self, root1: 'TreeNode', root2: 'TreeNode') -> bool:
# Base case: Both nodes are None (empty subtrees match)
if not root1 and not root2:
return True
# If one is None or values differ, they cannot be equivalent
if not root1 or not root2 or root1.val != root2.val:
return False
# Check two possibilities:
# 1. No flip at current node (Left matches Left, Right matches Right)
# 2. Flip occurred at current node (Left matches Right, Right matches Left)
no_flip = self.flipEquivalent(root1.left, root2.left) and \
self.flipEquivalent(root1.right, root2.right)
flip_occurred = self.flipEquivalent(root1.left, root2.right) and \
self.flipEquivalent(root1.right, root2.left)
return no_flip or flip_occurred
Edge Cases Handled
- Empty Trees: The
if not root1 and not root2condition returnsTrue, correctly handling two empty trees. - Mismatched Sizes/Structure: If one tree is exhausted (
None) while the other has nodes, it hitsnot root1 or not root2, returningFalse. - Value Mismatch: The check
root1.val != root2.valensures structural equivalence only happens if node values align. - Flip Requirement: By checking both direct and swapped child recursions (
no_flipORflip_occurred), we account for the specific operation allowed by the problem statement without modifying the tree structure in place (which would be space/time overhead to revert).