Flip Equivalent Binary Trees - Leetcode Solution

Problem Statement:

We are given the root nodes of two binary trees, root1 and root2. Suppose that root1 and root2 are flip equivalent.

Flip equivalence is defined as follows: We can flip the left and right nodes of a node in a binary tree. For example, consider the following two binary trees:

      1                       1
     / \                     / \
    2   3                   3   2
   / \                     
  4   5                     

The binary tree on the right is obtained by flipping the left and right children of the nodes 2 and 3 of the binary tree on the left.

Note that flipping a node's children means swapping the pointers to its left and right subtrees. For example, if a node has a left child pointing to node A and a right child pointing to node B, then after flipping the node, its left child should point to node B and its right child should point to node A.

Write a function to determine whether the two binary trees root1 and root2 are flip equivalent. You may assume that the root nodes of all trees are not null.

Solution:

We can solve this problem recursively. We start with the base case:

• If both roots are null, then they are flip equivalent. Return true.
• If either of the roots is null, then they are not flip equivalent. Return false.

Now, let's consider the recursive case. We need to check if the left and right children of root1 are flip equivalent to the left and right children of root2. There are two possibilities:

• The left and right children of root1 are flip equivalent to the left and right children of root2.
• The left and right children of root1 are flip equivalent to the right and left children of root2.

We can check both possibilities using the following code:

class Solution { public: bool flipEquiv(TreeNode* root1, TreeNode* root2) { // Base case if (root1 == nullptr && root2 == nullptr) { return true; } if (root1 == nullptr || root2 == nullptr) { return false; }

    // If the values of the roots are different, 
    // then the trees cannot be flip equivalent.
    if (root1->val != root2->val) {
        return false;
    }

    // Check if the left and right children of root1
    // are flip equivalent to the left and right
    // children of root2, or if they are flip equivalent
    // to the right and left children of root2.
    return (flipEquiv(root1->left, root2->left) && 
            flipEquiv(root1->right, root2->right)) || 
           (flipEquiv(root1->left, root2->right) && 
            flipEquiv(root1->right, root2->left));
}

};

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the binary trees. This is because we visit each node of the binary tree only once.

Space Complexity:

The space complexity of the above algorithm is O(h), where h is the height of the binary tree. This is the space used by the call stack during the recursive calls. In the worst case, the height of the binary tree is n, and the space complexity becomes O(n).

1