LeetCode Problem 951

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

LeetCode 951 - Flip Equivalent Binary Trees

Problem Understanding

This problem asks us to determine whether two binary trees can be made identical by performing a special operation called a flip. A flip operation can be applied at any node, and it simply swaps that node’s left and right child subtrees.

The important detail is that we are allowed to perform this operation any number of times, at any nodes in the tree. Two trees are considered flip equivalent if there exists some sequence of flips that transforms one tree into the other.

The input consists of two binary tree roots, root1 and root2. Each tree node contains an integer value and references to left and right children. The output should be true if the trees are flip equivalent, otherwise false.

The constraints are relatively small. Each tree contains at most 100 nodes, and all node values are unique within a tree. The uniqueness property is very important because it means that when comparing nodes, matching values identify corresponding positions unambiguously. Since the trees are small, recursive depth-first traversal is entirely practical.

Several edge cases are important to recognize immediately. If both trees are empty, they are trivially equivalent. If one tree is empty and the other is not, they cannot be equivalent. If two corresponding nodes have different values, no amount of flipping can make them match. Another subtle case occurs when one subtree must be matched normally while another must be matched after flipping. A naive comparison that only checks children in fixed left-to-right order would fail in such situations.

Approaches

Brute Force Approach

A brute-force solution would attempt every possible combination of flips. At every node, we have two choices: either flip the children or leave them unchanged. We could recursively generate all possible transformed versions of the first tree and compare each one with the second tree.

This approach is correct because it explicitly explores every possible arrangement obtainable through flips. If any transformed version matches the second tree exactly, then the trees are flip equivalent.

However, this method is extremely inefficient. For a tree with n nodes, each node potentially doubles the number of configurations. In the worst case, this creates O(2^n) possible tree structures. Even with only 100 nodes, this becomes computationally infeasible.

Optimal Depth-First Search Approach

The key observation is that we do not need to generate every possible flipped tree explicitly. Instead, we can compare the trees recursively while considering both possible matching configurations at each node.

Suppose we are comparing nodes a and b.

There are only two valid ways their subtrees could match:

1. Without a flip:

• a.left matches b.left
• a.right matches b.right

2. With a flip:

• a.left matches b.right
• a.right matches b.left

If either configuration succeeds recursively, then the current pair of nodes is flip equivalent.

This approach avoids constructing transformed trees entirely. Instead, it directly verifies equivalence through recursive structure matching.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries every possible flip combination
Optimal DFS	O(n)	O(h)	Recursively checks both matching possibilities

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

1. Start by comparing the current nodes from both trees.

If both nodes are None, they are equivalent because two empty trees match perfectly. 2. Check whether exactly one node is None.

If one node exists and the other does not, the trees cannot match, so return false. 3. Compare the node values.

If the values differ, no sequence of flips can make the nodes equal, so return false. 4. Recursively check the non-flipped configuration.

Compare:

• root1.left with root2.left
• root1.right with root2.right

If both recursive comparisons return true, then the subtrees match without needing a flip. 5. Recursively check the flipped configuration.

Compare:

• root1.left with root2.right
• root1.right with root2.left

If both recursive comparisons return true, then the subtrees match after flipping. 6. Return true if either configuration succeeds.

If neither configuration works, the trees are not flip equivalent.

Why it works

At every node, there are only two possible valid alignments between the children: either they already match in order, or they match after swapping left and right. The recursive algorithm exhaustively checks both possibilities at every node. Since every subtree must satisfy the same property recursively, the algorithm correctly determines whether the entire trees are flip equivalent.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def flipEquiv(
        self,
        root1: Optional[TreeNode],
        root2: Optional[TreeNode]
    ) -> bool:
        
        # Both nodes are empty
        if not root1 and not root2:
            return True

        # One node is empty
        if not root1 or not root2:
            return False

        # Values must match
        if root1.val != root2.val:
            return False

        # Check without flipping
        no_flip = (
            self.flipEquiv(root1.left, root2.left) and
            self.flipEquiv(root1.right, root2.right)
        )

        # Check with flipping
        flip = (
            self.flipEquiv(root1.left, root2.right) and
            self.flipEquiv(root1.right, root2.left)
        )

        return no_flip or flip

The implementation directly mirrors the recursive reasoning from the algorithm walkthrough.

The first section handles base cases. If both nodes are None, they are equivalent. If only one node is None, equivalence is impossible.

Next, the node values are compared. Since node values are unique, differing values immediately invalidate equivalence.

The algorithm then computes two recursive conditions. The no_flip condition checks whether the children match in their original positions. The flip condition checks whether the children match after swapping positions.

Finally, the method returns True if either recursive configuration succeeds.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {

    // Both nodes are nil
    if root1 == nil && root2 == nil {
        return true
    }

    // One node is nil
    if root1 == nil || root2 == nil {
        return false
    }

    // Values must match
    if root1.Val != root2.Val {
        return false
    }

    // Check without flipping
    noFlip := flipEquiv(root1.Left, root2.Left) &&
        flipEquiv(root1.Right, root2.Right)

    // Check with flipping
    flip := flipEquiv(root1.Left, root2.Right) &&
        flipEquiv(root1.Right, root2.Left)

    return noFlip || flip
}

The Go implementation follows exactly the same recursive structure as the Python version.

The main language-specific difference is the use of nil instead of None. Go also uses struct field access with capitalized names such as Val, Left, and Right.

Since node values are small integers and recursion depth is limited to at most 100 nodes, there are no integer overflow or recursion depth concerns in Go for this problem.

Worked Examples

Example 1

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]

The root nodes both contain value 1.

Step	root1 Node	root2 Node	Action
1	1	1	Values match
2	2	3	Direct match fails
3	2	2	Flip comparison succeeds
4	3	3	Flip comparison succeeds
5	5	5	Values match
6	7	8	Direct match fails
7	7	7	Flip comparison succeeds
8	8	8	Flip comparison succeeds

The recursive calls eventually confirm that every subtree can be aligned through flips, so the result is true.

Example 2

root1 = []
root2 = []

Step	root1 Node	root2 Node	Result
1	None	None	Return true

Both trees are empty, so they are trivially flip equivalent.

Example 3

root1 = []
root2 = [1]

Step	root1 Node	root2 Node	Result
1	None	1	Return false

One tree is empty while the other is not, so equivalence is impossible.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node pair is processed recursively
Space	O(h)	Recursive call stack depends on tree height

The algorithm visits corresponding nodes recursively. Since each node comparison performs constant work aside from recursive calls, the total running time is linear in the number of nodes.

The space complexity comes from recursion depth. In the worst case of a completely skewed tree, the recursion stack can grow to O(n). In a balanced tree, the recursion depth is O(log n).

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(5, TreeNode(7), TreeNode(8))
    ),
    TreeNode(3, TreeNode(6))
)

root2 = TreeNode(
    1,
    TreeNode(3, None, TreeNode(6)),
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(5, TreeNode(8), TreeNode(7))
    )
)

assert solution.flipEquiv(root1, root2) == True  # Complex flip equivalence

# Example 2
assert solution.flipEquiv(None, None) == True  # Both trees empty

# Example 3
assert solution.flipEquiv(None, TreeNode(1)) == False  # One empty tree

# Single node equal
assert solution.flipEquiv(TreeNode(1), TreeNode(1)) == True  # Same single node

# Single node different
assert solution.flipEquiv(TreeNode(1), TreeNode(2)) == False  # Different values

# Simple flip required
root1 = TreeNode(1, TreeNode(2), TreeNode(3))
root2 = TreeNode(1, TreeNode(3), TreeNode(2))
assert solution.flipEquiv(root1, root2) == True  # Root flip needed

# Different structure
root1 = TreeNode(1, TreeNode(2), None)
root2 = TreeNode(1, None, TreeNode(3))
assert solution.flipEquiv(root1, root2) == False  # Structure mismatch

# Larger equivalent trees
root1 = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
)

root2 = TreeNode(
    1,
    TreeNode(3),
    TreeNode(2, TreeNode(5), TreeNode(4))
)

assert solution.flipEquiv(root1, root2) == True  # Multiple flips

# Deep skewed trees
root1 = TreeNode(1, TreeNode(2, TreeNode(3)))
root2 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert solution.flipEquiv(root1, root2) == False  # Different shapes

Test	Why
Both trees empty	Validates base case handling
One tree empty	Ensures mismatch detection
Single equal nodes	Verifies simplest valid tree
Single different nodes	Verifies value comparison
Simple root flip	Tests direct child swapping
Different structure	Ensures structure matters
Multiple flips	Validates recursive flip handling
Deep skewed trees	Tests recursion on unbalanced trees

Edge Cases

One important edge case occurs when both trees are empty. A careless implementation might incorrectly return false because there are no nodes to compare. The correct behavior is to return true, since two empty trees are structurally identical. The implementation handles this immediately with the first base case.

Another important case is when exactly one node is None. This situation can happen at any depth in the recursion. If one subtree exists while the other does not, the trees cannot be made equivalent through flipping because flipping only swaps existing subtrees. The implementation explicitly checks for this condition before continuing recursion.

A third subtle edge case occurs when children only match after flipping. For example, one tree may store children as (2, 3) while the other stores (3, 2). A naive algorithm that only compares left-to-left and right-to-right would incorrectly return false. The implementation avoids this issue by checking both the normal and flipped configurations recursively.

A final important case involves deeply nested flips. Some trees require flips at multiple levels, not just the root. The recursive structure naturally handles this because every subtree independently checks both possible alignments. This ensures correctness even for complex nested transformations.