Flip Equivalent Binary Tree
Posted: 12 Mar, 2021
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.
All the values of the tree are unique.
For the given binary trees
Tree 1 can be made flip equivalent to Tree 2 by flipping the left and right sub trees of the node with value = 2.
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.
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
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)
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
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
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
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.
- Let flipEquivalent( ROOT1, ROOT2 ) be the recursive function.
- If ROOT1 and ROOT2 both are null, then we will simply return true.
- 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.
- 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.
- If ‘ROOT1’ = NULL and ‘ROOT2’ = NULL, return “true”.
- If ‘ROOT1’ = NULL or ‘ROOT2’ = NULL or ‘ROOT1 → DATA' ! = ‘ROOT2 → DATA’, return "false".
- Return ( flipEquivalent( ROOT1 -> LEFT, ROOT2 -> RIGHT ) && flipEquivalent( ROOT1 -> RIGHT, ROOT2 -> LEFT) Or flipEquivalent( ROOT1 -> LEFT, ROOT2 -> LEFT ) && flipEquivalent( ROOT1 -> RIGHT, ROOT2 -> RIGHT ).
Vertical Sum in BST
Posted: 27 Jul, 2021
Minimum Knight Moves
Posted: 20 Aug, 2021
Reverse A LL
Posted: 9 Sep, 2021
Collect Maximum Coins in Matrix
Posted: 29 Oct, 2021
BST from Preorder
Posted: 1 Nov, 2021