Flip Equivalent Binary Trees | Coding Challenge

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 root1 and root2, return true if the two trees are flip equivalent or false otherwise.

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.

Solution in Python Programming

Prerequisite:

• Binary Tree implementation in Python

Python Code:

# 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.