951. Flip Equivalent Binary Trees Solution

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

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 overview

Problem Overview: Two binary trees are flip equivalent if you can make them identical by repeatedly swapping the left and right children of any node. The task is to determine whether two given trees can become the same after any number of flips.

Approach 1: Recursive DFS Comparison (O(n) time, O(h) space)

The most natural solution uses recursion with Depth-First Search. Start from the root of both trees and compare nodes. If values differ, the trees cannot be equivalent. Otherwise, recursively check two possible configurations: (1) left with left and right with right, or (2) left with right and right with left. If either configuration returns true, the current nodes are flip equivalent. The recursion continues until all nodes match or a mismatch is found. Each node is visited once, giving O(n) time, while recursion depth depends on tree height O(h).

This approach works because flips only affect the order of children, not node values or subtree structure. By evaluating both possible pairings at every node, you effectively simulate every valid flip configuration without actually modifying the tree.

Approach 2: Iterative DFS Using Stack (O(n) time, O(n) space)

An iterative alternative uses an explicit stack instead of recursion. Push the root pair onto the stack and process nodes in DFS order. For each pair, compare values and determine whether children match directly or require a flip. Based on the match condition, push the correct child pairs onto the stack. This avoids recursion depth limits and gives more control over traversal. Time complexity remains O(n) since each node pair is processed once, while the stack may store up to O(n) nodes in skewed trees.

This method is useful in environments where recursion depth could overflow, especially with very deep tree structures.

Recommended for interviews: The recursive DFS solution is the expected answer. It is concise, directly models the flip logic, and clearly demonstrates understanding of binary tree traversal and subtree comparison. Interviewers usually look for the insight that two configurations must be checked at every node. The iterative stack version is a good follow‑up showing you can convert recursion into an explicit DFS implementation.

Approach 1: Recursive Approach

This approach uses a recursive function to check if both trees are identical or one is a flipped version of the other. For each pair of nodes, we check if subtree structures match directly or with a flip.

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        if not root1 and not root2:
            return True
        if not root1 or not root2 or root1.val != root2.val:
            return False
        
        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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null || 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++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2 || 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

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

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

#include <stdbool.h>

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

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool FlipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null || 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));
    }
}

Here, the Python implementation follows the recursive checking strategy using a Solution class method. It checks the required conditions at each node to ascertain if the trees are flip equivalent.

Complexity

Time Complexity: O(N).
Space Complexity: O(H).

Try this approach in the editor

Approach 2: Iterative Approach Using Stack

In this approach, instead of recursion, we use a stack for depth-first search. It proceeds similarly by evaluating if nodes are flip equivalent, but uses an explicit stack rather than the call stack.

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        stack = [(root1, root2)]
        while stack:
            n1, n2 = stack.pop()
            if not n1 and not n2:
                continue
            if not n1 or not n2 or n1.val != n2.val:
                return False
            
            if (n1.left and n2.left and n1.left.val == n2.left.val) or (not n1.left and not n2.left):
                stack.append((n1.left, n2.left))
                stack.append((n1.right, n2.right))
            else:
                stack.append((n1.left, n2.right))
                stack.append((n1.right, n2.left))
        return True

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var flipEquiv = function(root1, root2) {
    const stack = [[root1, root2]];
    while (stack.length) {
        const [n1, n2] = stack.pop();
        if (!n1 && !n2) continue;
        if (!n1 || !n2 || n1.val !== n2.val) return false;

        if ((n1.left && n2.left && n1.left.val === n2.left.val) || (!n1.left && !n2.left)) {
            stack.push([n1.left, n2.left]);
            stack.push([n1.right, n2.right]);
        } else {
            stack.push([n1.left, n2.right]);
            stack.push([n1.right, n2.left]);
        }
    }
    return true;
};

In this Python implementation, we use a stack to iteratively check node pairs. We continue popping nodes to compare for equivalency in both standard and flipped orientations until the stack is empty.

Complexity

Time Complexity: O(N).
Space Complexity: O(H), similar to the recursive approach.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function flipEquiv(root1: TreeNode | null, root2: TreeNode | null): boolean {
    if (root1 === root2) return true;
    if (!root1 || !root2 || root1?.val !== root2?.val) return false;

    const { left: l1, right: r1 } = root1!;
    const { left: l2, right: r2 } = root2!;

    return (flipEquiv(l1, l2) && flipEquiv(r1, r2)) || (flipEquiv(l1, r2) && flipEquiv(r1, l2));
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
	var dfs func(root1, root2 *TreeNode) bool
	dfs = func(root1, root2 *TreeNode) bool {
		if root1 == root2 || (root1 == nil && root2 == nil) {
			return true
		}
		if root1 == nil || root2 == nil || root1.Val != root2.Val {
			return false
		}
		return (dfs(root1.Left, root2.Left) && dfs(root1.Right, root2.Right)) || (dfs(root1.Left, root2.Right) && dfs(root1.Right, root2.Left))
	}
	return dfs(root1, root2)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Approach	Time Complexity: O(N). Space Complexity: O(H).
Iterative Approach Using Stack	Time Complexity: O(N). Space Complexity: O(H), similar to the recursive approach.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive DFS Comparison	O(n)	O(h)	Best general solution. Clean logic and preferred in interviews.
Iterative DFS Using Stack	O(n)	O(n)	Useful when avoiding recursion or handling very deep trees.

Frequently asked questions

Is Flip Equivalent Binary Trees easy or hard?

Flip Equivalent Binary Trees is generally considered a medium difficulty problem. The recursion itself is simple, but recognizing that you must check two subtree configurations at every node is the key insight.

Flip Equivalent Binary Trees Python/Java solution

Both Python and Java implementations follow the same logic: compare node values, then recursively check normal and flipped child configurations. Python often uses a concise recursive function, while Java typically defines a helper method that compares subtree pairs.

How to solve Flip Equivalent Binary Trees in O(n)?

Traverse both trees simultaneously using DFS. For every pair of nodes, check if their values match. Then recursively verify either (left-left and right-right) or (left-right and right-left). Because each node is processed once and only two comparisons are made per node, the total runtime stays O(n).

What is the best approach for Flip Equivalent Binary Trees?

Recursive depth‑first search is the most common solution. At each node you compare values and recursively verify two possibilities: normal child order or flipped order. If either combination matches, the subtrees are flip equivalent. This approach runs in O(n) time and uses O(h) space for recursion.

Is Flip Equivalent Binary Trees asked at Google/Amazon/Meta?

Tree comparison and subtree matching problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving tree transformations or structural equivalence are common because they test recursion and DFS reasoning.

What data structure is used in Flip Equivalent Binary Trees?

The problem operates on a binary tree and is typically solved using depth‑first search. Recursion implicitly uses a call stack, while iterative solutions use an explicit stack to simulate DFS traversal.

What is the time complexity of Flip Equivalent Binary Trees?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node pair is compared at most once during the DFS traversal. Space complexity is O(h) for recursion stack depth, where h is the height of the tree.

Flip Equivalent Binary Trees solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach

Approach 2: Iterative Approach Using Stack

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Flip Equivalent Binary Trees solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach

Approach 2: Iterative Approach Using Stack

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems