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.

Description Solution Video 11:06

951. Flip Equivalent Binary Trees

Medium69.8% acceptance4 companies

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

Asked at 4 companies

Anduril

Google Amazon Microsoft

Topics

11:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3,4,5,6,null,null,null,7,8]
[1,3,2,null,6,4,5,null,null,null,null,8,7]

Input

[]
[]

Input

[]
[1]

Your code is saved on this device.Solution