Leetcode 951. Flip Equivalent Binary Trees

Problem Explanation

The problem is about determining if two binary trees could become the same tree after some number of "flip" operations. A flip operation is defined as choosing any node, and swapping the left and right child subtrees.

For example, suppose we have two binary trees:

1
2
3Tree 1:          1
4               /   \
5             2      3
6           /   \   
7         4      5  
8               /  \
9              7    8
10
11Tree 2:          1
12               /   \  
13              3     2
14                  /   \
15                4     5
16                      / \
17                     8   7
18

If we perform flip operations on nodes with values 1, 3, and 5 of tree 2, then tree 1 and tree 2 will become the same. Therefore, these two trees are considered flip equivalent.

The problem asks us to create a function that takes two binary trees as inputs and returns true if they are flip equivalent and false otherwise.

Approach

The solution uses a recursive approach, traversing through both trees simultaneously. During each recursive call, it checks the following conditions:

• If both current nodes are null, then return true. This means both trees are completely traversed and found to be flip equivalent.
• If either of the current nodes is null, then return false. This means one tree has more nodes than the other.
• If the values of the current nodes are not equal, then return false. This means even after making flips, we cannot make corresponding nodes equal.

If none of the above conditions are true, then consider two cases:

• Flipping is not needed. Thus, the method is called recursively for the left child of the first tree and the left child of the second tree. And it's again called for the right child of the first tree and the right child of the second tree.
• Flipping is needed. Thus, the method is called recursively for the left child of the first tree and the right child of the second tree. And its again called for the right child of the first tree and the left child of the second tree.

If either case is true, then the function returns true, else false.

Python Solution

1
2python
3class Solution:
4    def flipEquiv(self, root1, root2):
5        if root1 is None:
6            return root2 is None
7        if root2 is None:
8            return root1 is None
9        if root1.val != root2.val:
10            return False
11        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))

Java Solution

1
2java
3class Solution {
4    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
5        if (root1 == null)
6            return root2 == null;
7        if (root2 == null)
8            return root1 == null;
9        if (root1.val != root2.val)
10            return false;
11        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
12               (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4  flipEquiv(root1, root2) {
5    if (root1 === null) {
6      return root2 === null;
7    }
8    if (root2 === null) {
9      return root1 === null;
10    }
11    if (root1.val !== root2.val) {
12      return false;
13    }
14    return (this.flipEquiv(root1.left, root2.left) && this.flipEquiv(root1.right, root2.right)) ||
15           (this.flipEquiv(root1.left, root2.right) && this.flipEquiv(root1.right, root2.left));
16  }
17}

C++ Solution

1
2c++
3class Solution {
4public:
5    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
6        if (root1 == nullptr)
7            return root2 == nullptr;
8        if (root2 == nullptr)
9            return root1 == nullptr;
10        if (root1->val != root2->val)
11            return false;
12        return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) ||
13               (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public bool FlipEquiv(TreeNode root1, TreeNode root2) {
5        if (root1 == null)
6            return root2 == null;
7        if (root2 == null)
8            return root1 == null;
9        if (root1.val != root2.val)
10            return false;
11        return (FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right)) ||
12               (FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left));
13    }
14}

Time and Space Complexity Analysis

The time complexity of all the solutions is O(n), since in the worst-case scenario, we need to visit each node of both trees. Here, n is the number of nodes in the larger tree.

The space complexity is O(h), where h is the height of the tree. This is because the maximum depth of the recursion call stack will be proportional to the height of the tree. In the worst-case scenario, this will be a completely unbalanced tree, and h will be equal to n.

Code Optimization

The solutions above are already optimized and use a simple recursive approach to solve the problem. However, you can make the code cleaner and easier to read by encapsulating the null check into a separate helper function. For example:

1
2python
3def isEqual(self, node1, node2): 
4    if not node1 or not node2: 
5        return node1 == node2 
6    return node1.val == node2.val
7
8def flipEquiv(self, root1, root2): 
9    if not self.isEqual(root1, root2): 
10        return False
11    if root1 is None: 
12        return True
13    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)

This way, we can avoid repeating the null checks in each recursive call and also make the code more straightforward and readable.

Conclusion

To sum up, this problem revolves around tree traversal and manipulation. Understanding how binary trees work and how to traverse them recursively is essential for this problem. The problem also deals with the idea of tree transformations by swapping child nodes, which is an interesting concept that can come handy in various tree-related problems. By understanding and solving such problems, you can enhance your data structure and problem-solving skills effectively.