Find Duplicate Subtrees
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 comparing subtrees without doing redundant work. Comparing every pair of subtrees directly is quadratic in the number of nodes, and each comparison can itself cost linear time. A better route is to represent each subtree as a string (a serialization) so that two subtrees are duplicates if and only if their serializations match. That turns "compare tree structures" into "find duplicate strings," which a hash map handles in constant time per lookup.
Key Constraints:
1 <= number of nodes <= 5000-- An O(n^2) approach is feasible at this size, but the serialization strings themselves can grow to O(n) characters on a skewed tree, so a naive string approach degrades to O(n^2) total work. The ID-based approach below avoids that.-200 <= Node.val <= 200-- Values can be negative, so the serialization has to keep the sign and a delimiter. Writing the raw digits with no separator would let different trees collide, which the next sections make precise.At least 1 node-- There is no empty-tree edge case to handle.
Approach 1: Brute Force (Compare All Pairs)
Intuition
For every node in the tree, check whether the subtree rooted at it is identical to the subtree rooted at some earlier node. The first time a structure shows up again, it is a duplicate and we record it once.
To check whether two subtrees are identical, compare them recursively: the roots hold the same value, the left subtrees match, and the right subtrees match.
The challenge is reporting each duplicate structure exactly once even when it appears three or more times. We solve that by counting how many earlier nodes match the current one. A node is the second occurrence of its structure precisely when exactly one earlier node matches it, so we add it then and never again.
This does a lot of repeated work. There are O(n^2) pairs of nodes, and each comparison can visit O(n) nodes in the worst case, giving an O(n^3) running time.
Algorithm
- Collect all nodes in the tree into a list using any traversal.
- For each node i, count how many earlier nodes (indices 0 to i-1) root a subtree identical to the one at node i.
- To check identity, recursively compare the two subtrees: same value, same left subtrees, same right subtrees.
- If that count is exactly 1, node i is the second occurrence of its structure, so add it to the result. A third or later occurrence has a count of 2 or more, so it is skipped and never duplicated.
- Return the result list.
Visualization and Code
Loading animation...
- 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
isSameuses O(h) space where h is the tree height (O(n) for a skewed tree).
The cost comes from comparing every pair of subtrees from scratch. The next approach builds a compact fingerprint for each subtree once, so comparison becomes a hash map lookup.
Approach 2: Postorder Serialization with Hash Map
Intuition
Instead of comparing subtrees structurally, serialize each subtree into a string. Two subtrees are identical if and only if their serializations match, which turns the tree comparison into string matching.
We build the serialization with a postorder traversal (left, right, node) so it grows bottom-up. For each node, we take the serialization of its left subtree, the serialization of its right subtree, and the current node's value, then join them. A null child becomes a marker like #.
Each serialization goes into a hash map keyed by the string, with a count of occurrences. The first time a string appears its count is 1; the second time it reaches 2, which is when we record the current node as a duplicate. Later occurrences are ignored, so each duplicate structure is added exactly once.
The delimiter between fields is load-bearing, not decoration. Consider serializing a node with value 1 whose only child is a leaf with value 2, versus a single leaf with value 12. Without separators, the first could read as 122 (something like value 1, child 2, plus null markers) and a different tree could produce the same run of characters, so two distinct trees would collide and be reported as duplicates. The value range here makes this concrete: values can be negative and multi-digit, so 2 followed by 1 must not be confused with 21. Writing the comma between every field, and a distinct # for null, guarantees the string parses back to exactly one tree, so equal strings mean equal trees.
Two subtrees produce the same serialization if and only if they have the same shape and the same values. The if direction is immediate. For the only if direction, the delimiters make the string uniquely decodable: a serialization can be parsed back into one and only one tree, so two equal strings cannot come from two different structures. Building postorder guarantees that when a node is serialized, both children are already serialized, so the count of a string equals the number of identical subtrees seen so far.
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.
Visualization and Code
Loading animation...
- 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 cost comes from the string serialization itself. On a skewed tree, the total string data across all nodes reaches O(n^2). The next approach replaces each long string with a short, fixed-size identifier.
Approach 3: ID-Based Serialization (Optimal)
Intuition
The string approach pays for long serializations because a parent's string contains the full serialization of both children, which contains the full serialization of the grandchildren, and so on. Each subtree's representation copies everything below it.
Instead, assign each distinct subtree structure a numeric ID. A subtree is then described by three numbers: the left child's ID, the current node's value, and the right child's ID. This is a fixed-size tuple regardless of subtree depth, the same way a reference to a document by its page number is fixed-size no matter how long the document is. Two subtrees are identical exactly when they map to the same tuple, so the same tuple maps to the same ID. The ID of a subtree built from those three numbers is shared across every occurrence of that structure, which is why counting IDs is enough to detect duplicates.
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.
Visualization and Code
Loading animation...
- Time Complexity: O(n) for the hash-based implementations. We visit each node once and do O(1) amortized work per node: forming a bounded-length key plus hash map lookups and inserts. The C++ version keys an ordered
mapon a tuple (sinceunordered_maphas no built-in tuple hash), making it O(n log n); switching to a string key or a custom tuple hash restores O(n). - 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 (O(n) for a skewed tree).
A related variant replaces the integer IDs with a hash computed from the children's hashes and the node value, a Merkle-style hash-of-children scheme. It keeps the O(n) running time and constant-size keys without maintaining a separate ID counter, at the cost of handling hash collisions (two different subtrees mapping to the same hash). The ID-based approach sidesteps collisions entirely because distinct tuples always get distinct IDs, so it is the safer default for an exact-match requirement.