Leetcode Daily Question 24/10/2024 - 951. Flip Equivalent Binary Trees

Problem Description:

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.

from typing import Optional

class TreeNode:
  def __init__(self, val = 0, left = None, right = None):
    self.val = val
    self.left = left
    self.right = right
    
    
class Solution:
  
  # Version 1: DFS
  def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode]) -> bool:
      if not node1 and not node2:
        return True
      if not node1 or not node2 or node1.val != node2.val:
        return False
      
      same = dfs(node1.left, node2.left) and dfs(node1.right, node2.right)
      flip = dfs(node1.left, node2.right) and dfs(node1.right, node2.left)
      
      return same or flip
    
    return dfs(root1, root2)
  
  
  # Version 2: BFS
  def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if not self.match(root1, root2):
      return False
    
    queue = deque([(root1, root2)])
    
    while queue:
      node1, node2 = queue.popleft()
      if not self.match(node1, node2):
        return False
      
      children1 = (node1.left, node1.right)
      children2 = (node2.left, node2.right)
      
      if self.match(children1[0], children2[0]) and self.match(children1[1], children2[1]):
        queue.append((node1.left, node2.left))
        queue.append((node1.right, node2.right))
      
      elif self.match(children1[1], children2[0]) and self.match(children1[0], children2[1]): 
        queue.append((node1.left, node2.right))
        queue.append((node1.right, node2.left))
      
      else:
        return False
    return True
  
  def match(self, node1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if not node1 and not node2:
      return True
    if not node1 or not node2 or node1.val != node2.val:
      return False
    return True

Explanation:

We can solve this by traversing both trees and comparing node by node to see if they and their children matches, up to flipping the nodes.

We can do this either with dfs or bfs. I shall present both solutions as they follow very similar train of thoughts.

During dfs, we explore one node at a time in both trees, and see
1. if they match
2. if their children match (up to flipping)

So take the following trees as an example:

# Tree1
    1
   / \
  3   4

# Tree2
    1
   / \
  4   3

Tree1 node 1 = TreeNode(1)
Tree2 node 1 = TreeNode(1)

These nodes matches so we continue to the children.

Tree1 node 1.left = TreeNode(3)
Tree2 node 1.left = TreeNode(4)

When not flipped the nodes are not matched. So we proceed to also check the flipped nodes.

Tree1 node 1.left = TreeNode(3)
Tree2 node 1.right = TreeNode(3)

Tree1 node 1.right = TreeNode(4)
Tree2 node 1.left = TreeNode(4)

These matches, so we return True.

Here is the DFS version.

def dfs(node1: Optional[TreeNode], node2: Optional[TreeNode]) -> bool:
      if not node1 and not node2:
        return True
      if not node1 or not node2 or node1.val != node2.val:
        return False
      
      same = dfs(node1.left, node2.left) and dfs(node1.right, node2.right)
      flip = dfs(node1.left, node2.right) and dfs(node1.right, node2.left)
      
      return same or flip
    
    return dfs(root1, root2)

For BFS the idea is exactly the same. We keep a double ended queue and track the current node value or each tree.

We de-queue the node from each tree and compare them first, then the children. If the node and children of the non-flipped or flipped nodes matches, we append them as a pair back into the queue and continue exploring level by level.

We also use a separate function to encapsulate the checking logic to make the code more slick.

def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if not self.match(root1, root2):
      return False
    
    queue = deque([(root1, root2)])
    
    while queue:
      node1, node2 = queue.popleft()
      if not self.match(node1, node2):
        return False
      
      children1 = (node1.left, node1.right)
      children2 = (node2.left, node2.right)
      
      if self.match(children1[0], children2[0]) and self.match(children1[1], children2[1]):
        queue.append((node1.left, node2.left))
        queue.append((node1.right, node2.right))
      
      elif self.match(children1[1], children2[0]) and self.match(children1[0], children2[1]): 
        queue.append((node1.left, node2.right))
        queue.append((node1.right, node2.left))
      
      else:
        return False
    return True
  
  def match(self, node1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if not node1 and not node2:
      return True
    if not node1 or not node2 or node1.val != node2.val:
      return False
    return True

The time complexity of either version is O(n) as we traverse each node once and both tree simultaneously.

The space complexity is O(n) for BFS in the worst case as we store the nodes in each level with the widest being the last level with up to n / 2 nodes.

The space complexity is O(h) for DFS where h is the height of tree. Even though DFS is more efficient than BFS in terms of memory usage. It still requires the repeated use of a call stack.

The full solution for both versions can be found near the top of the page.