Find Duplicate Subtrees
Last Updated: April 3, 2026
Understanding the Problem
We are given a binary tree, and we need to find all subtrees that appear more than once. A subtree here means a node along with all of its descendants, preserving structure. Two subtrees are considered duplicates only if they have the exact same shape and the same values at every position.
The challenge is figuring out how to efficiently compare subtrees. A naive approach would compare every pair of subtrees directly, but that is wasteful. The key observation is that we can represent each subtree as a unique string (a serialization), and then two subtrees are duplicates if and only if they produce the same string. This transforms the problem from "compare tree structures" to "find duplicate strings," which is something a hash map handles naturally.
Key Constraints:
1 <= number of nodes <= 5000-- With n up to 5000, even an O(n^2) approach is feasible (25 million operations), but we should aim for better. An O(n) or O(n * average_string_length) solution is ideal.-200 <= Node.val <= 200-- Node values are bounded integers. This is useful because it means serialized representations will not have extremely long individual node strings.At least 1 node-- No need to handle an empty tree.
Approach 1: Brute Force (Compare All Pairs)
Intuition
The most straightforward idea: for every pair of nodes in the tree, check if the subtrees rooted at those two nodes are identical. If they are, add one of them to the result (making sure we do not add duplicates).
To check if two subtrees are identical, we do a recursive comparison: same value at the root, and both left subtrees are identical, and both right subtrees are identical.
This is conceptually simple but does a lot of redundant work. For each of the O(n^2) pairs, the comparison itself can take O(n) time in the worst case, making this an O(n^3) approach.
Algorithm
- Collect all nodes in the tree into a list using any traversal.
- For every pair of distinct nodes (i, j), check if the subtree rooted at node i is identical to the subtree rooted at node j.
- To check identity, recursively compare the two subtrees: same value, same left subtrees, same right subtrees.
- If a duplicate pair is found, add the root of one subtree to the result set (use a set to avoid adding the same structure multiple times).
- Return the result list.
Example Walkthrough
Input:
We compare every pair of subtrees. Node 4 appears as a leaf in three places (indices 3, 9, and 6). When we compare node at index 3 with node at index 9, isSame returns true, so we add [4] to the result. Similarly, the subtree [2, 4] appears at indices 1 and 5, so we add [2, 4] to the result.
Output:
Code
- Time Complexity: O(n^3). We have O(n^2) pairs of nodes, and each
isSamecomparison can visit up to O(n) nodes in the worst case. - Space Complexity: O(n). The list of all nodes takes O(n) space, and the recursion stack for
isSamegoes up to O(h) where h is the tree height.
The bottleneck is comparing every pair of subtrees from scratch. What if we could represent each subtree with a compact fingerprint so that comparison becomes an O(1) hash map lookup?
Approach 2: Postorder Serialization with Hash Map
Intuition
Instead of comparing subtrees structurally, we can serialize each subtree into a string. Two subtrees are identical if and only if their serializations match. This transforms a tree comparison problem into a string matching problem.
We use postorder traversal (left, right, node) to build the serialization bottom-up. For each node, we recursively get the serialization of its left subtree and right subtree, then combine them with the current node's value. A null child is represented by a special marker like "#".
We store each serialization in a hash map counting occurrences. When the count for a serialization hits exactly 2, we know we have found a duplicate, and we add the current node to our result.
The serialization captures everything about a subtree: its structure (where the nulls are) and its values. Because we build it postorder (bottom-up), by the time we process a parent node, both children have already been serialized. So the parent's serialization naturally includes the full representation of its entire subtree.
Using the count == 2 check is a clean trick. When we see a serialization for the first time (count = 1), we just note it. When we see it a second time (count = 2), we know it is a duplicate, so we add it to the result. If we see it a third, fourth, or fifth time, we skip it because we have already recorded this pattern.
Algorithm
- Initialize a hash map to count serialization occurrences and a result list.
- Perform a postorder DFS on the tree.
- At each node, build the serialization:
leftSerial + "," + rightSerial + "," + node.val. - For null nodes, return "#" as the serialization.
- Increment the count for this serialization in the hash map.
- If the count becomes exactly 2, add the current node to the result list.
- Return the serialization string so the parent can use it.
- After the DFS completes, return the result list.
Example Walkthrough
Code
- Time Complexity: O(n^2). We visit each node once, but building the serialization string involves concatenating strings. In the worst case (a skewed tree), the serialization of the root is O(n) characters long. Across all nodes, the total string construction work can be O(n^2).
- Space Complexity: O(n^2). The hash map stores serialization strings. In the worst case, the total length of all stored strings is O(n^2) on a skewed tree where serializations grow linearly.
The bottleneck is the string serialization itself. For a skewed tree, the total string data across all nodes can reach O(n^2). What if we could represent each subtree with a short, fixed-size identifier instead of a long string?
Approach 3: ID-Based Serialization (Optimal)
Intuition
The string serialization approach works, but it suffers from long strings in the worst case. Here is the optimization: instead of encoding a subtree as a full string, we assign each unique subtree structure a numeric ID. Then, to represent a subtree, we only need three things: the left child's ID, the current node's value, and the right child's ID. That is a fixed-size tuple, no matter how deep the subtree is.
Think of it like this. In the string approach, the parent's serialization includes the entire serialization of both children, which includes the entire serialization of the grandchildren, and so on. It is like copying a document into another document into another document. With IDs, we just reference the document by its page number instead of copying it. Each node's representation is always just three numbers.
Algorithm
- Initialize a map from tuple (leftID, nodeVal, rightID) to a unique integer ID, starting IDs from 1. Reserve ID 0 for null nodes.
- Initialize a count map from ID to occurrence count, and a result list.
- Perform a postorder DFS.
- For null nodes, return ID 0.
- At each node, recursively get the left child's ID and right child's ID.
- Form the tuple (leftID, node.val, rightID).
- If the tuple is not in the map, assign it a new ID.
- Look up the ID for this tuple and increment its count.
- If the count equals 2, add the current node to the result.
- Return the ID for this subtree.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once. At each node, we do O(1) work: building a short key string of bounded length, and hash map lookups/inserts that are O(1) amortized.
- Space Complexity: O(n). The tupleToId map stores at most n entries (one per unique subtree pattern). The idCount map also stores at most n entries. The recursion stack uses O(h) space where h is the tree height.