Vultr DocsLatest Content

Flip Equivalent Binary Trees

Updated on 29 May, 2025
Flip Equivalent Binary Trees header image

Problem Statement

In this scenario, we are dealing with binary trees and a specific operation known as a "flip operation." A flip involves choosing any node within a binary tree and swapping its left and right child subtrees. The primary challenge is to determine whether two given binary trees, denoted as X and Y, can be rendered identical through a series of these operations. The trees are considered flip equivalent if it's possible to transform tree X into tree Y using any number of flips. The function should return true if the trees are flip equivalent and false otherwise, based on the roots root1 and root2 of these binary trees.

Examples

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].

Approach and Intuition

To tackle the problem of determining whether two trees are flip equivalent, observe the nature of the flip operation and utilize a recursive strategy.

  1. Begin by examining the simplest case: if both trees are empty (i.e., the roots root1 and root2 are null). In this scenario, the trees are trivially flip equivalent, and we should return true.

  2. Next, consider the case where one tree is empty, and the other is not. This situation directly leads to a false result, as an empty tree cannot be made equivalent to a non-empty tree through any number of flips.

  3. For trees that are not empty, compare the root values of root1 and root2. If these values differ, return false immediately as differing root values cannot be reconciled through subtree flips.

  4. If the roots are the same, recursively check two potential scenarios due to the flip's nature:

    • The left child of root1 might become equivalent to either the left child of root2 or its right child (and similarly for the right child). Thus, check the flip equivalency by recursively assessing:

      • (root1.left, root2.left) and (root1.right, root2.right) for regular child alignment.
      • (root1.left, root2.right) and (root1.right, root2.left) for flipped child alignment.

  5. The trees are flip equivalent if either of the recursive conditions stated above holds true for subtree checks.

By following this recursive approach, each node and its respective children are compared against the potential flip equivalents. The use of recursion leverages the inherently nested structure of the subtree swappings, making the solution both intuitive and efficient within the given constraints.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    void toCanonical(TreeNode* node) {
        if (!node) return;

        toCanonical(node->left);
        toCanonical(node->right);

        if (!node->right) return;
        if (!node->left) {
            node->left = node->right;
            node->right = NULL;
            return;
        }

        TreeNode* lChild = node->left;
        TreeNode* rChild = node->right;
        if (lChild->val > rChild->val) {
            node->left = rChild;
            node->right = lChild;
        }
    }

    bool checkEquivalent(TreeNode* n1, TreeNode* n2) {
        if (!n1 && !n2) return true;
        if (!n1 || !n2) return false;
        if (n1->val != n2->val) return false;

        return checkEquivalent(n1->left, n2->left) &&
               checkEquivalent(n1->right, n2->right);
    }

    bool flipEquivalent(TreeNode* n1, TreeNode* n2) {
        toCanonical(n1);
        toCanonical(n2);
        return checkEquivalent(n1, n2);
    }
};

This solution aims to determine whether two binary trees are flip equivalent. Flip equivalent means one tree can be transformed into the other by flipping some of the children nodes. The solution consists of three main member functions of the Solution class, implemented in C++:

  • toCanonical: This function is designed to transform any given tree into a canonical form. By recursively visiting each node, it ensures that if a node has both children, the left child must not have a higher value than the right child. If the left child is null and the right is not, it swaps them to maintain consistency in the structure.

  • checkEquivalent: This function compares two trees to verify if they are structurally and value-wise identical. It recursively checks each corresponding node and their children from both trees.

  • flipEquivalent: This function integrates toCanonical and checkEquivalent. It first converts both input trees into their canonical forms and then checks whether these forms are equivalent.

To use the above functions effectively, consider this flow:

  1. Instantiate the Solution class.
  2. Call the flipEquivalent function with the roots of the two binary trees you want to compare.

This structure ensures that the trees are compared in a standardized form, increasing the function's efficiency and reliability in checking for equivalency post potential flips.

java 
class Solution {

    public void bringToCanonical(TreeNode node) {
        if (node == null) return;

        bringToCanonical(node.left);
        bringToCanonical(node.right);

        if (node.right == null) return;

        if (node.left == null) {
            node.left = node.right;
            node.right = null;
            return;
        }

        TreeNode leftChild = node.left;
        TreeNode rightChild = node.right;

        if (leftChild.val > rightChild.val) {
            node.left = rightChild;
            node.right = leftChild;
        }
    }

    public boolean treesMatch(TreeNode first, TreeNode second) {
        if (first == null && second == null) return true;
        if (first == null || second == null) return false;
        if (first.val != second.val) return false;

        return (
            treesMatch(first.left, second.left) &&
            treesMatch(first.right, second.right)
        );
    }

    public boolean areFlipEquivalent(TreeNode firstRoot, TreeNode secondRoot) {
        bringToCanonical(firstRoot);
        bringToCanonical(secondRoot);
        return treesMatch(firstRoot, secondRoot);
    }
}

The provided Java solution focuses on determining if two binary trees are flip equivalent. Flip equivalence means the trees can be made identical by flipping some of the children in the binary trees. A methodical approach is adopted that involves three main methods inside a Solution class:

  1. bringToCanonical(TreeNode node): This method ensures each node in the binary tree adheres to a canonical form where the left child has a value less than or equal to the right child. It recursively processes the entire tree and flips the children of a node if necessary.

    • Ensure recursive canonicalization of left and right children.
    • Correctly handle cases where nodes might not have both children present.
    • Flip children if the left child's value exceeds the right child's value.

  2. treesMatch(TreeNode first, TreeNode second): This function recursively checks if two binary trees are identical without any further flipping.

    • Return true if both trees are null (base case of recursion).
    • Recursively verify that the structures and values of corresponding nodes in both trees match.

  3. areFlipEquivalent(TreeNode firstRoot, TreeNode secondRoot): This method is the entry point for checking flip equivalence.

    • First, convert both trees to their canonical forms using bringToCanonical.
    • Use treesMatch to determine if the two canonical trees are identical.

The solution effectively uses recursion to achieve the checking and flipping of trees, ensuring that it adheres to optimized memory usage and computational efficiency. Ensure both trees are traversed in a deep-first manner, considerably managing the canonical structuring before performing the final match comparison.

python 
class Solution:
    def normalize_tree(self, node: TreeNode) -> None:
        if not node:
            return

        # Process children first
        self.normalize_tree(node.left)
        self.normalize_tree(node.right)

        # If no right child, no need to swap
        if not node.right:
            return

        # Ensure left child is present
        if not node.left:
            node.left, node.right = node.right, None
            return
        lhs = node.left
        rhs = node.right

        # Ensure left value is smaller
        if lhs.val > rhs.val:
            node.left, node.right = node.right, node.left

    def trees_match(self, t1: TreeNode, t2: TreeNode) -> bool:
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        return self.trees_match(t1.left, t2.left) and self.trees_match(t1.right, t2.right)

    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        self.normalize_tree(root1)
        self.normalize_tree(root2)
        return self.trees_match(root1, root2)

The provided Python code introduces a solution to determine if two binary trees are flip equivalent, meaning they are identical or could be made identical by flipping some of their children.

  • The implementation comprises a class Solution with three methods: normalize_tree, trees_match, and flipEquiv.

  • The normalize_tree method ensures each sub-tree keeps the smaller value on the left:

    1. Recursively normalize its child nodes.
    2. Swap the children if the left node is missing or the left value is greater than the right.

  • The trees_match method checks if two trees are structurally and value-wise equivalent:

    1. Recursively compare both left and right subtrees.
    2. Ensure the corresponding nodes have the same value.

  • The flipEquiv method first normalizes both input trees using normalize_tree and then compares them using trees_match to determine if they are identical or not.

This solution efficiently normalizes the tree representations to facilitate a simple comparison, leveraging recursion to simplify both structural modifications and the equivalence check.

Comments

No comments yet.