951. Flip Equivalent Binary Trees LeetCode Solution

In this guide, you will get 951. Flip Equivalent Binary Trees LeetCode Solution with the best time and space complexity. The solution to Flip Equivalent Binary Trees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Flip Equivalent Binary Trees solution in C++
Flip Equivalent Binary Trees solution in Java
Flip Equivalent Binary Trees solution in Python
Additional Resources

951. Flip Equivalent Binary Trees LeetCode Solution image

Problem Statement of Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

Example 1:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

Example 2:

Input: root1 = [], root2 = []
Output: true

Example 3:

Input: root1 = [], root2 = [1]
Output: false

Constraints:

The number of nodes in each tree is in the range [0, 100].
Each tree will have unique node values in the range [0, 99].

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

951. Flip Equivalent Binary Trees LeetCode Solution in C++

class Solution {
 public:
  bool flipEquiv(TreeNode* root1, TreeNode* root2) {
    if (root1 == nullptr)
      return root2 == nullptr;
    if (root2 == nullptr)
      return root1 == nullptr;
    if (root1->val != root2->val)
      return false;
    return flipEquiv(root1->left, root2->left) &&
               flipEquiv(root1->right, root2->right) ||
           flipEquiv(root1->left, root2->right) &&
               flipEquiv(root1->right, root2->left);
  }
};
/* code provided by PROGIEZ */

951. Flip Equivalent Binary Trees LeetCode Solution in Java

class Solution {
  public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if (root1 == null)
      return root2 == null;
    if (root2 == null)
      return root1 == null;
    if (root1.val != root2.val)
      return false;
    return //
        flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) ||
        flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
  }
}
// code provided by PROGIEZ

951. Flip Equivalent Binary Trees LeetCode Solution in Python

class Solution:
  def flipEquiv(self, root1: TreeNode | None, root2: TreeNode | None) -> bool:
    if not root1:
      return not root2
    if not root2:
      return not root1
    if root1.val != root2.val:
      return False
    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))
 # code by PROGIEZ