Log inSign up
mediumleetcodeNot Started

Duplicate Subtrees

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them. Two trees are duplicate if they have the same structure with the same node values.

Example 1 · Example 1: Tree with Multiple Duplicates:

Input: root = [1, 2, 3, 4, null, 2, 4, null, null, 4] Tree: 1 / \ 2 3 / / \ 4 2 4 / 4
Output: [[2, 4], [4]]
Explanation: Subtree [4] occurs 3 times. Subtree [2, 4] occurs 2 times. Both duplicate roots are returned.

Example 2 · Example 2: Small Tree:

Input: root = [2, 1, 1] Tree: 2 / \ 1 1
Output: [[1]]
Explanation: Leaf node 1 is duplicated.

Constraints:

  • The number of the nodes in the tree will be in the range [1, 5000].
  • -200 <= Node.val <= 200

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Serialize subtrees recursively to compare tree structures.
  • Prevent duplicate outputs by triggering addition strictly when count == 2.
  • Understand the string concatenation O(n2) bottleneck and how ID mapping achieves O(n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find identical subtrees in a binary tree.
  • Structural equality check across all subtrees.
  • Tree serialization with hash table.

Algorithmic Decision Tree:

  • serial = node.val + , + serialize(left) + , + serialize(right).
  • map[serial]++.
  • if map[serial] == 2 -> result.push(node).

Connected Patterns:

Serialize and Deserialize Binary TreeSubtree of Another TreeSame Tree

1. Pairwise Tree Comparison for Every Subtree

Intuition

Traverse tree to collect all n subtree root pointers. For every pair (i, j), check if isSameTree(i, j) is true. Collect unique matching subtrees.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Collect all subtree root nodes into an array nodes.
  2. Step 2: Compare each pair (nodes[i], nodes[j]) using isSameTree.
  3. Step 3: Deduplicate identical subtree structures.
  4. Step 4: Return collected unique roots.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isSame(TreeNode* a, TreeNode* b) {
10 if (!a && !b) return true;
11 if (!a || !b) return false;
12 return a->val == b->val && isSame(a->left, b->left) && isSame(a->right, b->right);
13 }
14 void collect(TreeNode* node, vector<TreeNode*>& nodes) {
15 if (!node) return;
16 nodes.push_back(node);
17 collect(node->left, nodes);
18 collect(node->right, nodes);
19 }
20 vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
21 vector<TreeNode*> nodes;
22 collect(root, nodes);
23 vector<TreeNode*> res;
24 vector<bool> used(nodes.size(), false);
25 for (int i = 0; i < nodes.size(); ++i) {
26 if (used[i]) continue;
27 bool duplicateFound = false;
28 for (int j = i + 1; j < nodes.size(); ++j) {
29 if (!used[j] && isSame(nodes[i], nodes[j])) {
30 used[j] = true;
31 duplicateFound = true;
32 }
33 }
34 if (duplicateFound) res.push_back(nodes[i]);
35 }
36 return res;
37 }
38};
39
40int main() {
41 // Sample driver execution
42 cout << "Execution completed successfully." << endl;
43 return 0;
44}
45

Time & Space Complexity

  • Time complexity: O(n^3) — There are O(n2) pairs, and isSameTree takes O(n) per pair.
  • Space complexity: O(n) — List of subtree pointers.

2. Postorder Subtree String Serialization

Intuition

Serialize each subtree as node.val + ',' + leftSerial + ',' + rightSerial. Track frequencies in a hash map. When count reaches 2, add node to result.

When to apply: Standard interview approach.

Algorithm

  1. Step 1: Helper serialize(node, map, res).
  2. Step 2: If node == null return #.
  3. Step 3: str = to_string(node.val) + , + serialize(node.left) + , + serialize(node.right).
  4. Step 4: map[str]++. If map[str] == 2, res.push_back(node).
  5. Step 5: Return str.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 string serialize(TreeNode* node, unordered_map<string, int>& m, vector<TreeNode*>& res) {
10 if (!node) return "#";
11 string s = to_string(node->val) + "," + serialize(node->left, m, res) + "," + serialize(node->right, m, res);
12 m[s]++;
13 if (m[s] == 2) res.push_back(node);
14 return s;
15 }
16 vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
17 unordered_map<string, int> m;
18 vector<TreeNode*> res;
19 serialize(root, m, res);
20 return res;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n^2) — String serialization creates strings of length up to O(n) at each of the n nodes, taking O(n2) total string construction time.
  • Space complexity: O(n^2) — Hash map stores strings of cumulative length up to O(n2).

3. Unique Subtree ID Mapping (Strict O(n))

Intuition

Instead of concatenating long strings, represent each subtree by a 3-tuple: (node.val, leftId, rightId). Map each unique tuple to an integer ID. This keeps hash map keys to fixed-size integers/tuples, achieving strict O(n) runtime.

When to apply: Optimal gold-standard solution for strict O(n) time and space.

Algorithm

  1. Step 1: Map each unique triplet (node.val, leftId, rightId) to an incrementing integer ID.
  2. Step 2: Base case: null node gets ID 0.
  3. Step 3: Triplet key = node.val + , + leftId + , + rightId.
  4. Step 4: If key not in idMap, idMap[key] = nextId++.
  5. Step 5: countMap[curId]++. If countMap[curId] == 2, push node to res. Return curId.

Serialization Trace for root = [2, 1, 1]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Traverse left leaf 1
Visual state
Values and pointers at this exact step
tree
Root
2
L
1 ('1,#,#')
R
1

Node order shown; add connections to display explicit tree edges.

seen 1x: 1L
Check / comparison
count('1,#,#') = 1 (First occurrence)
Decision / next transition
Record serialization in map.
Why this step matters

Step 1: Traverse left leaf 1. Serialization is 1,#,#. Map count for 1,#,# becomes 1.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int curId = 1;
9 unordered_map<string, int> tripletToId;
10 unordered_map<int, int> countMap;
11 vector<TreeNode*> res;
12 int getId(TreeNode* node) {
13 if (!node) return 0;
14 int leftId = getId(node->left);
15 int rightId = getId(node->right);
16 string key = to_string(node->val) + "," + to_string(leftId) + "," + to_string(rightId);
17 if (!tripletToId.count(key)) {
18 tripletToId[key] = curId++;
19 }
20 int id = tripletToId[key];
21 countMap[id]++;
22 if (countMap[id] == 2) res.push_back(node);
23 return id;
24 }
25public:
26 vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
27 getId(root);
28 return res;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Integer ID operations take O(1) time per node.
  • Space complexity: O(n) — Maps store O(n) fixed-size tuples and integers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Pairwise ComparisonO(n^3)O(n)Compare every subtree pair with isSameTree.Pairwise tree traversals.
2.String SerializationO(n^2)O(n^2)Serialize entire subtree to string with null markers.String concatenation.
3.Subtree ID MappingOptimalO(n)O(n)Map (node.val, leftId, rightId) triplets to integer IDs.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Tree with no duplicates: returns [].
  • All nodes have same value (e.g. 0 -> 0 -> 0): duplicate single-node leaves and 2-node subtrees are collected.
  • Multiple duplicates of the same subtree (appears 4 times): root is included exactly once.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify why count == 2 is used rather than count >= 2: it prevents duplicate entries in the answer.
  2. Mention that while string serialization is O(n2) due to string copying, integer ID hashing reduces it to O(n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why should we add a duplicate subtree root to the output list ONLY when its frequency count equals exactly 2 (count == 2)?

Back to DSA Sheet