Flip Equivalent Binary Trees - Practice Coding Problems

Flip Equivalent Binary Trees - Problem

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.

Input & Output

Example 1 — Flip Equivalent Trees

$ 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

💡 Note: Tree2 can be obtained from Tree1 by flipping the children of nodes 1 and 3

Example 2 — Empty Trees

$ Input: root1 = [], root2 = []

› Output: true

💡 Note: Both trees are empty, so they are flip equivalent

Example 3 — Different Structure

$ Input: root1 = [], root2 = [1]

› Output: false

💡 Note: One tree is empty while the other has nodes, cannot be flip equivalent

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]

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Two binary trees with same values but different structure

Flip Operations

Swap left and right children at any node

Check Equivalence

Determine if trees can be made identical

Key Takeaway

🎯 Key Insight: At each node, check both original and flipped child arrangements recursively

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that at each node, we need to check both orientations: original (left-left, right-right) and flipped (left-right, right-left). Best approach is DFS recursion with O(n) time and O(h) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Flips	O(2^n)	O(2^n)	Generate all possible flip combinations and check if any matches target tree
DFS Recursive Approach	O(n)	O(h)	Recursively check if trees are flip equivalent using depth-first search

Brute Force - Generate All Flips — Algorithm Steps

Generate all 2^n possible flip combinations for tree1
For each configuration, compare with tree2
Return true if any match found

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Tree

Start with tree1 in original form

Generate Flips

Create all 2^n possible flip combinations

Compare Each

Check if any configuration matches tree2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool areSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p->val == q->val && areSameTree(p->left, q->left) && areSameTree(p->right, q->right);
}

bool solution(struct TreeNode* root1, struct TreeNode* root2) {
    // Simplified brute force approach
    return areSameTree(root1, root2);
}

int main() {
    // Simplified implementation
    printf("false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Need to generate 2^n possible flip combinations where n is number of nodes

⚠ Quadratic Growth

Space Complexity

O(2^n)

Store all possible tree configurations plus recursion stack

⚠ Quadratic Space

85.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Flips — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler