Flip Equivalent Binary Trees

Medium · Graphs · Explanation and code example

Iterative DFS

How it works

This is the iterative version of the recursive DFS approach, using an explicit stack instead of the call stack. We process node pairs from the stack, checking values and pushing child pairs in the appropriate order (direct or flipped).

Steps

Initialize a stack with the pair (root1, root2).
While the stack is not empty:
- Pop a pair of nodes.
- If either is null, verify both are null. If not, return false.
- If their values differ, return false.
- Determine child pairing: if left children match (both null or same value), push direct pairs. Otherwise, push flipped pairs.
Return true if all pairs are processed successfully.

Complexity

Time complexity: O(n)
Space complexity: O(n)

Things to watch for

Forgetting to Check Both Flip Orderings

A common mistake is only checking if the trees match directly without considering the flipped case. The problem allows flipping at any node, so you must check both scenarios: (1) left matches left AND right matches right, OR (2) left matches right AND right matches left. Missing either case will produce incorrect results.

Incorrect Null Handling in Base Cases

When comparing nodes, both null checks must be handled carefully. If only one node is null (but not both), the trees cannot be equivalent. Returning true when only one is null, or forgetting to handle the case where both are null, leads to incorrect behavior.

Not Checking Node Values Before Recursing

Before exploring children, you must verify that the current nodes have the same value. Skipping this check and directly comparing children can cause false positives when nodes at the same position have different values but happen to have structurally similar subtrees.

Python code example

from typing import Optional

# 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
class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        stack = [(root1, root2)]

        while stack:
            node1, node2 = stack.pop()

            if not node1 or not node2:
                if node1 != node2:
                    return False
                continue

            if node1.val != node2.val:
                return False

            if ((node1.left and node2.left and
                 node1.left.val == node2.left.val) or
                (not node1.left and not node2.left)
            ):
                stack.append((node1.left, node2.left))
                stack.append((node1.right, node2.right))
            else:
                stack.append((node1.left, node2.right))
                stack.append((node1.right, node2.left))

        return True

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        stack<pair<TreeNode*, TreeNode*>> stk;
        stk.push({root1, root2});

        while (!stk.empty()) {
            auto [node1, node2] = stk.top();stk.pop();

            if (!node1 || !node2) {
                if (node1 != node2) return false;
                continue;
            }

            if (node1->val != node2->val) return false;

            if ((node1->left && node2->left && node1->left->val == node2->left->val) ||
                (!node1->left && !node2->left)) {
                stk.push({node1->left, node2->left});
                stk.push({node1->right, node2->right});
            } else {
                stk.push({node1->left, node2->right});
                stk.push({node1->right, node2->left});
            }
        }

        return true;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations