Flip Equivalent Binary Tree

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in companies
AdobeUberApple

Problem statement

You have been given the root of two binary trees ‘ROOT1’ and ‘ROOT2’. You need to find if the two trees are flip equivalent or not after performing some flip operations on ‘TREE1’.

A flip operation is defined as: Choose any node and swap the left and right subtrees of that node.

Note: 
All the values of the tree are unique.
For Example: 
For the given binary trees

binarytree

Tree 1 can be made flip equivalent to Tree 2 by flipping the left and right sub trees of the node with value = 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases. Then the test cases are as follows.

The first and second line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

tree

For example, the input for the tree depicted in the above image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Note: 
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format: 
For each test, print “Yes” if the two trees are flip equivalent. Otherwise, print “No”.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
0 <= N <= 10^3
1 <= DATA <= 10^4

Where ‘N’ is the total number of nodes in the binary tree, and “DATA” is the value of the binary tree node.

Time Limit: 1 sec
Sample Input 1:
2
7 9 13 8 -1 4 2 -1 -1 -1 -1 -1 -1
7 13 9 2 4 8 -1 -1 -1 -1 -1 -1 -1
14 2 -1 5 -1 -1 -1
16 -1 2 5 -1 -1 -1
Sample Output 1:
Yes
No
Explanation Of Sample Input 1:
Test Case 1: The binary tree in the first test case will be

Tree 

If we flip left and right subtrees of Tree1 having node values 7 and 13, the resulting tree will become equivalent to Tree2. Therefore given two trees are flip equivalent.

Test Case 2: As the value of the root node in both the trees are different. So they can never be flip equivalent to each other.
Sample Input 2:
2
8 21 17 -1 -1 -1 -1
8 21 -1 17 -1 -1 -1
5 10 -1 15 -1 -1 -1
5 -1 10 15 -1 -1 -1
Sample Output 2:
No
Yes
Explanation Of Sample Input 2:
Test Case 1: As the left subtree and right subtree of the root node in both the trees are different. So they can never be flip equivalent to each other.

Test Case 2: If we flip right subtree of Tree1 to left subtree of root node, the resulting tree will become equivalent to Tree2. Therefore given two trees are flip equivalent.
Hint

Recursively check for every node of the tree.

Approaches (2)
Recursion

Approach: A simple idea to check if the tree is flip equivalent or not is to use recursion. We will recursively check for every node.

  1. Let flipEquivalent( ROOT1, ROOT2 ) be the recursive function.
  2. If ROOT1 and ROOT2 both are null, then we will simply return true.
  3. If either ROOT1 is null, ROOT2 is null or ROOT1 -> DATA is not equal to ROOT2-> DATA, return false as we can not make the trees flip equivalent in any of these cases.
  4. If ROOT1 and ROOT2 have the same data, then we will check for their child nodes. There will be two cases for that.
    • Either we need to flip the left and right sub-tree of root1 or there will be no need for that.
    • If we flip left and right subtree we will recursively check
      • flipEquivalent( ROOT1 -> LEFT, ROOT2 -> RIGHT ) && flipEquivalent( ROOT1→ RIGHT, ROOT2 -> LEFT )
    • If we do not flip, we will check  flipEquivalent( ROOT1 -> LEFT,  ROOT2 -> LEFT ) && flipEquivalent( ROOT1 -> RIGHT, ROOT2 -> RIGHT ).
    • Return bitwise OR  of the above two cases.

 

Algorithm:

  1. If ‘ROOT1’ = NULL and ‘ROOT2’ = NULL, return “true”.
  2. If ‘ROOT1’ = NULL or ‘ROOT2’ = NULL or ‘ROOT1 → DATA' ! = ‘ROOT2 → DATA’, return "false".
  3. Return ( flipEquivalent( ROOT1 -> LEFT, ROOT2 -> RIGHT ) &&  flipEquivalent( ROOT1 -> RIGHT, ROOT2 -> LEFT)  Or  flipEquivalent( ROOT1 -> LEFT, ROOT2 -> LEFT ) &&  flipEquivalent( ROOT1 -> RIGHT, ROOT2 -> RIGHT ).
Time Complexity

O(min( N1, N2 )), where N1 and N2 are the numbers of nodes in Tree1 and Tree2.

 

We are recursively checking for every node and this recursion will be stopped when we reach the end of either of the two trees. Therefore Time complexity is O(min(N1, N2)).

Space Complexity

O(min(N1, N2), where N1 and N2 are the numbers of nodes in Tree1 and Tree2.

 

The maximum number of recursive calls at a time can be min (N1, N2). So space used by the stack for these recursive calls makes the space complexity O(min(N1, N2).

Code Solution
(100% EXP penalty)
Flip Equivalent Binary Tree
Full screen
Console