This is one of the popular coding challenges on the binary tree.
Let’s understand the flip operation first.
For a binary tree, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
What are flip equivalent binary trees?
A binary tree T1 is flip equivalent to a binary tree T2 if and only if we can make T1 equal to T2 after some number of flip operations.
Problem Statement: Given the roots of two binary trees
true if the two trees are flip equivalent or
Note: This is one of the competitive coding challenges that was asked to me in the Teachmint coding interview round.
The difficulty level is intermediate or medium.
Explanation with an example:
Consider below two binary trees.
These two binary trees are flip equivalent as we can get one binary tree from another by flipping nodes 1, 3 and 5.
# 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 flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool: if root1 is None and root2 is None: return True elif root1 and root2: if root1.val == root2.val: return ( self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) ) or ( self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left) ) else: return False else: return False
Hope this code is self-explanatory., If you have any doubts or have a better solution, let’s discuss it in the comment section below.
If you are preparing for a coding interview, you can solve this coding question in any programming language of your choice like C/C++, Java, Python, etc.