Flip Equivalent Binary Trees

Medium
1933.

Flip Equivalent Binary Trees

Flip Equivalent Binary Trees is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

A flip on a binary tree chooses one node and swaps its left and right subtrees.

Two trees are flip equivalent if some sequence of flips (possibly none) turns the first into the second. Given the roots root1 and root2 of two binary trees, each with distinct values, return true if they are flip equivalent and 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
Flip the children of 1, of 3 and of 5 in the first tree and you get the second.

Example 2

Input
root1 = [1,2,3,4], root2 = [1,3,2,4]
Output
false
Explanation
In the first tree 4 hangs under 2, in the second under 3. Flips only swap a node's two children, so they can never move 4 to another parent.

Example 3

Input
root1 = [], root2 = []
Output
true
Explanation
Two empty trees are equivalent without any flip.

Constraints

  • The number of nodes in each tree is in the range [0, 100]
  • Each tree has unique node values in the range [0, 99]
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var flipEquiv = function(root1, root2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Flip Equivalent Binary Trees — Problem & Solution

Flip Equivalent Binary Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Flip Equivalent Binary Trees is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A flip on a binary tree chooses one node and swaps its left and right subtrees.

Two trees are flip equivalent if some sequence of flips (possibly none) turns the first into the second. Given the roots root1 and root2 of two binary trees, each with distinct values, return true if they are flip equivalent and 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: Flip the children of 1, of 3 and of 5 in the first tree and you get the second.

Example 2

Input: root1 = [1,2,3,4], root2 = [1,3,2,4]
Output: false
Explanation: In the first tree 4 hangs under 2, in the second under 3. Flips only swap a node's two children, so they can never move 4 to another parent.

Example 3

Input: root1 = [], root2 = []
Output: true
Explanation: Two empty trees are equivalent without any flip.

Constraints

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

Hints for Flip Equivalent Binary Trees

  1. Hint 1

    Flips never change which node is whose parent — only the left/right order. So the roots must match first.

  2. Hint 2

    Then the pair of children must match as a pair: either left with left and right with right, or left with right and right with left.

  3. Hint 3

    Recurse: equiv(a, b) is true when both are null, false when exactly one is null or the values differ, and otherwise one of the two pairings must be equivalent on both sides.

How to solve Flip Equivalent Binary Trees

A flip only reorders a node's two children, so two trees are flip equivalent exactly when their roots agree and their children can be paired up — straight or crossed — into flip-equivalent subtrees. That is a direct recursion.

Approach

  1. If both nodes are null, return true; if only one is null, return false.
  2. If their values differ, return false.
  3. Return (equiv(a.left, b.left) && equiv(a.right, b.right)) || (equiv(a.left, b.right) && equiv(a.right, b.left)).

Why it works

Any sequence of flips can be reordered so that the flip at the root (if any) is decided first and the rest act independently inside the two subtrees; so the trees match exactly when one of the two pairings matches recursively. With distinct values, at most one pairing can have matching child roots, so the recursion does constant work per node.

Complexity

  • Time — O(min(n1, n2)) with distinct values
  • Space — O(h) for the recursion

Pitfalls

  • Compare values before recursing; otherwise the two-way branching can explode.
  • Two empty trees are equivalent; an empty and a non-empty tree are not.
  • Matching the multiset of values is not enough — the parent of every node must agree.

Reference solution

Python

from typing import Optional

def flipEquiv(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if root1 is None or root2 is None:
        return root1 is root2
    if root1.val != root2.val:
        return False
    return (flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)) or \
        (flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left))

Java

public static boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) return root1 == root2;
    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));
}

C++

bool flipEquiv(TreeNode* root1, TreeNode* root2) {
    if (!root1 || !root2) return root1 == root2;
    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));
}

JavaScript

var flipEquiv = function(root1, root2) {
    if (root1 === null || root2 === null) return root1 === root2;
    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));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals