Abstract / Summary

Identify all subtrees that appear more than once in a binary tree and list their root 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 61% (500k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Hash Table
• 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 defines a Solution class with a single public method findDuplicateSubtrees. The method receives the root of a binary tree and produces an iterator that yields the root nodes of all sub-trees that appear more than once in the input. The algorithm works by serializing each sub-tree into a canonical string, counting how many times each serialization occurs, and emitting a node the moment its serialization is observed for the second time.

Key Steps

Serialization with memoization

@cache  # from problem 572
def serialize(node):
    if node:
        return "l=" + serialize(node.left) + "|" + str(node.val) + "|r=" + serialize(node.right)
    else:
        return ""

The serialize helper converts a subtree into a deterministic string. The format explicitly marks the left and right parts (l= and r=) and separates them with pipe characters. By decorating the function with @cache, the result for each distinct TreeNode instance is stored after the first computation, so subsequent calls for the same node reuse the cached value instead of rebuilding the string.

Counting occurrences

all = defaultdict(int)

A defaultdict of integers tracks how many times each serialization has been seen. The dictionary key is the serialization string, and the value is the current count.

Depth-first traversal and duplicate detection

def deeper(node):
    if node:
        s = serialize(node)
        all[s] += 1
        if all[s] == 2:  # emit second tree's root node
            yield node

        yield from deeper(node.left)
        yield from deeper(node.right)

The deeper generator performs a pre-order depth-first walk. For each visited node it obtains the serialized representation, increments the associated counter, and yields the node only when the counter reaches exactly two. This ensures that each duplicate subtree root is emitted once, regardless of how many additional copies exist later in the traversal.

Producing the final iterator

yield from deeper(root)

The method concludes by delegating to the deeper generator, allowing callers to iterate over the duplicate subtree roots directly.

Edge Cases Handled

When the input tree is empty (root is None), the deeper generator receives a None node, immediately returns without yielding, and the overall method produces an empty iterator.

A tree consisting of a single node cannot contain duplicate sub-trees; the serialization for that node is counted once, never reaching the threshold of two, so no values are yielded.

The serialization function returns an empty string for None children. This explicit representation prevents different structural configurations from collapsing into the same string (e.g., a node with only a left child versus a node with only a right child).

If multiple distinct sub-trees share the same shape and values, each distinct root will be serialized identically, causing the counter to increase. The generator yields the root of the second occurrence and ignores further repetitions, satisfying the requirement to report each duplicate group exactly once.

Performance Optimizations

The use of @cache on the serialize function eliminates redundant recomputation of subtree strings. Without caching, each node’s serialization would be recomputed for every ancestor that references it, leading to exponential work in the worst case. Memoization reduces the cost to a single serialization per node.

Counting with a defaultdict(int) provides O(1) amortized updates for each serialization, avoiding explicit existence checks.

The algorithm yields results lazily via a generator (deeper). This approach avoids constructing an intermediate list of all duplicate roots, which could be large for trees with many repeated patterns. Consumers can process each duplicate as soon as it is discovered, reducing peak memory usage.

By performing the count increment and duplicate check immediately after serialization, the method avoids a second pass over the tree. The entire detection process completes in a single depth-first traversal, combining counting and result emission in one cohesive step.

Imagine that a big tree is made of many smaller branches, and sometimes those branches look exactly the same. The goal of this code is to find all the parts of the tree that are twins.

The first part of the code acts like a tiny camera. It takes a picture of a branch and turns everything it sees into a special secret code made of words and symbols. If the code sees two branches that are identical, the secret code for both of them will be exactly the same. That helps verify if they are twins.

The second part of the code acts like a curious explorer. It starts at the very top of the big tree and walks down every single path to visit every branch. As it visits each piece, it uses the camera to get the secret code for that branch and writes it down in a notebook.

Every time the explorer writes down a code, it checks its notebook to see if that same code has been seen before. If the notebook shows that this is the second time the explorer has found this specific pattern, it knows it has found a twin. It then picks up that branch and puts it into a special bag so it can be shown to everyone at the end. The explorer keeps walking until every single tiny branch has been checked.

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

not analyzed yet

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		Rust			Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	Dijkstra-Edu		Java
	everthis				JS
	fartem						Ruby
	fengvyi	C++
	haoel			Python
	JoshCrozier				JS
	lkwq007			Python
	MacJim	C++
	ruoru					Rust
	suxrobGM							C#
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
haoel	Python
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
zfang399	C++

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