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.

Aniruddha Chaudhari

I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.