Abstract / Summary

Two binary trees are considered equivalent if one can be made identical to the other by swapping left and right children of any nodes.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (300k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether two binary trees are flip-equivalent. Two trees are flip-equivalent when they can be made identical by swapping the left and right children of any number of nodes. The algorithm builds a compact representation for each tree that captures the unordered pair of child values for every node, then compares these representations for equality.

Mapping Child Relationships

A central idea is to associate each node value with a tuple that records the values of its two children in sorted order. By sorting the two child values, the representation becomes insensitive to left-right swaps.

if node.left and node.right:
    one = node.left.val
    two = node.right.val
    pairs[node.val] = (min(one, two), max(one, two))
elif node.left:
    pairs[node.val] = (node.left.val, None)
elif node.right:
    pairs[node.val] = (node.right.val, None)
else:
    pairs[node.val] = (None, None)

This snippet ensures that for any node the tuple reflects the unordered set of child values, using None as a placeholder when a child is absent.

Recursive Traversal

The helper function deeper walks the tree depth-first, populating the dictionary with the mappings described above. The recursion visits the left subtree first, then the right subtree, guaranteeing that every node is processed exactly once.

def deeper(node, pairs):
    if node:
        # mapping logic …
        deeper(node.left, pairs)
        deeper(node.right, pairs)

The guard if node: prevents attempts to access attributes of a None reference, thereby handling empty subtrees gracefully.

Dictionary Construction

Two separate dictionaries, a and b, are created for the two input trees. Each dictionary key is a node value, and the associated value is the sorted child tuple.

a = {}
deeper(root1, a)
b = {}
deeper(root2, b)

Because dictionaries provide constant-time look-ups, the later comparison step can be performed efficiently.

Comparison Phase

After both dictionaries are built, the algorithm first checks that they contain the same number of entries. A mismatch in size immediately indicates non-equivalence.

if len(a) != len(b):
    return False

The subsequent loop iterates over the keys of the first dictionary, confirming that each key exists in the second dictionary and that the stored tuples match exactly.

for x in a:
    if x not in b:
        return False
    if a[x] != b[x]:
        return False

If all keys are present and all tuples agree, the function returns True, confirming flip-equivalence.

Edge Cases Handled

The implementation correctly processes trees that are completely empty; both root1 and root2 being None result in empty dictionaries, and the length check passes, leading to a True result. Single-node trees are also handled: the node’s entry receives a tuple of (None, None), and equality is determined by matching node values and identical tuples.

Nodes with only one child are represented with a tuple containing the child’s value and None. This representation distinguishes a missing left child from a missing right child only through the unordered nature of the tuple, which aligns with the flip-equivalence definition where the side of a solitary child does not matter.

Duplicate values across different nodes do not cause ambiguity because the dictionary keys are node values; the algorithm assumes node values are unique identifiers. Within the constraints of the problem, this assumption holds, and the code correctly maps each distinct value to its child pair.

Performance Optimizations

The algorithm leverages several implicit optimizations. By storing the sorted child pair directly in the dictionary, it avoids the need for later sorting or additional data structures during comparison. The early exit conditions-checking dictionary size before iterating, and returning immediately upon a missing key or mismatched tuple-prevent unnecessary work when a discrepancy is detected early in the process.

Using a depth-first recursion eliminates the overhead of an explicit stack, and the recursion depth is bounded by the height of the tree, which is natural for tree traversals. The constant-time dictionary operations for insertion and lookup keep the overall work proportional to the number of nodes, without extra passes over the data.

Imagine two family trees made of building blocks. Every block has a number on it, and each block can have smaller blocks attached underneath it like little children. This code is trying to find out if two of these structures are actually the same, even if some of the children decided to swap places and stand on the other side.

To figure this out, the computer starts by walking through the first tree from top to bottom. Every time it finds a block, it looks at the numbers on the children attached to it. It makes a little note card for that block that says exactly what numbers its children have, and it always puts the smaller number first so the order does not get confusing. It keeps these note cards in a big list called a dictionary.

Then, the computer goes back to the start and does the exact same thing for the second tree. It makes a new list of note cards for all those blocks too.

Finally, the computer brings the two lists of note cards together to compare them. It checks if there are the same number of blocks in both trees. Then it looks at every note card from the first tree and checks if there is a matching note card in the second tree that shows the same children. If every single block has a perfect match for its children, the trees are considered the same.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python					TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	JS			Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem						Ruby
	fengvyi	C++
	fsq	C++
	gouthampradhan		Java
	haoel			Python
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	lzl124631x	C++
	suxrobGM					C#
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fsq	C++
gouthampradhan	Java
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality