Find Duplicate Subtrees
Medium · Graphs · Explanation and code example
Depth First Search (Optimal)
How it works
The serialization approach has quadratic space complexity because string concatenation creates long strings for large trees. We can optimize by assigning a unique integer ID to each distinct subtree structure. Instead of storing full serialization strings, we represent each subtree as a tuple of (left_id, value, right_id) and map this tuple to a unique ID. This keeps the key size constant regardless of subtree depth.
Steps
- Perform a post-order DFS traversal, returning
-1fornullnodes. - For each node, create a tuple:
(left_child_id, node_value, right_child_id). - If this tuple is new, assign it a fresh unique ID.
- Track how many times each ID has been seen.
- When an ID is seen for the second time, add the current node to the result.
- Return the current subtree's ID for use by parent nodes.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Not Distinguishing Left and Right Children in Serialization
A serialization like "1,2,null" is ambiguous without structure markers. The value 2 could be a left child or right child. Always use a consistent format that distinguishes left from right, such as "value,left_serialization,right_serialization" with explicit null markers for missing children.
Adding Duplicates Multiple Times to the Result
When the same subtree structure appears three or more times, you should only add one representative to the result list. Track how many times each serialization has been seen and only add to the result on the second occurrence, not subsequent ones.
Quadratic Space from String Concatenation
Naive string serialization creates strings proportional to subtree size, leading to O(n^2) total space for all serializations. The optimized approach assigns unique integer IDs to each subtree structure, keeping the representation size constant regardless of subtree depth.
Python code example
from typing import List, Optional
from collections import defaultdict
# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
id_map = {}
count = defaultdict(int)
res = []
def dfs(node):
if not node:
return -1
cur = (dfs(node.left), node.val, dfs(node.right))
if cur not in id_map:
id_map[cur] = len(id_map) + 1
curId = id_map[cur]
if count[curId] == 1:
res.append(node)
count[curId] += 1
return curId
dfs(root)
return res
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 {
unordered_map<string, int> idMap;
unordered_map<int, int> count;
vector<TreeNode*> res;
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
dfs(root);
return res;
}
private:
int dfs(TreeNode* node) {
if (!node) return -1;
string cur = to_string(dfs(node->left)) + "," +
to_string(node->val) + "," +
to_string(dfs(node->right));
if (idMap.find(cur) == idMap.end()) {
idMap[cur] = idMap.size();
}
int curId = idMap[cur];
count[curId]++;
if (count[curId] == 2) {
res.push_back(node);
}
return curId;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.