# Find Duplicate Subtrees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-duplicate-subtrees)
Canonical: https://scaleengineer.com/dsa/problems/find-duplicate-subtrees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** Hash Table, Tree, Binary Tree
**Companies:** [Yandex](https://scaleengineer.com/companies/yandex), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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:**

![](https://assets.glich.co/dsa/find-duplicate-subtrees/image0.jpg) 

**Input:** root = [1,2,3,4,null,2,4,null,null,4]
**Output:** [[2,4],[4]]

**Example 2:**

![](https://assets.glich.co/dsa/find-duplicate-subtrees/image1.jpg) 

**Input:** root = [2,1,1]
**Output:** [[1]]

**Example 3:**

![](https://assets.glich.co/dsa/find-duplicate-subtrees/image2.jpg) 

**Input:** root = [2,2,2,3,null,3,null]
**Output:** [[2,3],[3]]

**Constraints:**

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

# Approaches
## Post-order Traversal with String Serialization
This approach involves traversing the tree and, for each node, creating a string representation (serialization) of the subtree rooted at that node. A hash map is used to store the frequency of each unique serialized string. When a subtree's serialization is encountered for the second time, it signifies a duplicate, and the root node of that subtree is added to the result list.
**Time:** O(N^2), where N is the number of nodes. In the worst case (a skewed tree), the depth of the recursion is N, and the serialized strings can have a length of O(N). Creating and hashing these long strings at each node leads to an O(N^2) complexity. · **Space:** O(N^2), where N is the number of nodes. The hash map can store up to N unique serializations. In the worst case of a skewed tree, the total length of all stored strings can be on the order of 1 + 2 + ... + N, which is O(N^2).
**Pros:** Conceptually simple to understand.; Correctly identifies all duplicate subtrees.
**Cons:** Can be inefficient in terms of time and space due to long string creation and storage.; String concatenation in a loop can lead to quadratic time complexity in the worst-case scenario (a skewed tree).
### Explanation
We can uniquely identify any subtree by serializing it into a string. A post-order traversal is a natural fit for this because to serialize a node, we first need the serialization of its children. 

We'll define a recursive helper function that traverses the tree. For each node, it first recursively serializes its left and right children. Then, it combines the node's own value with the children's serializations to form a unique string for the subtree rooted at the current node. For example, a representation could be `node.val,left_serialization,right_serialization`. A null child can be represented by a special marker like `#`.

As we generate these serialization strings, we use a hash map to keep track of how many times we've seen each one. When the count for a particular string reaches 2, we know we've found a duplicate subtree. We then add the current node (which is the root of this duplicate subtree) to our result list. We only add it when the count is exactly 2 to ensure each kind of duplicate is added only once.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        Map<String, Integer> counts = new HashMap<>();
        serialize(root, counts, result);
        return result;
    }

    private String serialize(TreeNode node, Map<String, Integer> counts, List<TreeNode> result) {
        if (node == null) {
            return "#";
        }
        String leftSerial = serialize(node.left, counts, result);
        String rightSerial = serialize(node.right, counts, result);
        
        String serial = node.val + "," + leftSerial + "," + rightSerial;
        
        counts.put(serial, counts.getOrDefault(serial, 0) + 1);
        
        if (counts.get(serial) == 2) {
            result.add(node);
        }
        
        return serial;
    }
}
```
### Algorithm
- Define a recursive helper function, `serialize(node, counts, result)`, that performs a post-order traversal.
- The base case for the recursion is a null node, for which we return a special marker string like `"#"`.
- For a non-null node, first recursively call the function for its left and right children to get their serialized strings: `leftSerial` and `rightSerial`.
- Construct the serialization for the current node by concatenating its value with the serializations of its children, separated by a delimiter (e.g., `node.val + "," + leftSerial + "," + rightSerial`).
- Use a hash map `counts` to store the frequency of each serialized string.
- Increment the count for the current serialization string in the map.
- If the count for the current serialization becomes exactly `2`, it means we have found this subtree once before. Add the current `node` to the `result` list.
- The function returns the serialization string for the current node.
- The main function initializes the map and the list and calls the helper function with the root of the tree.

## Post-order Traversal with Unique IDs
This is an optimized approach that avoids the overhead of creating and storing long strings. Instead of serializing the entire subtree into a string, we assign a unique integer ID to each distinct subtree structure. A post-order traversal is used, and for each node, a key is formed from its value and the IDs of its left and right children. This key is then mapped to a unique ID. A separate map tracks the frequency of these IDs to find duplicates.
**Time:** O(N), where N is the number of nodes. Each node is visited exactly once. The work done at each node (creating a triplet string, map lookups, and insertions) is constant on average. · **Space:** O(N), where N is the number of nodes. The maps used to store `triplet -> ID` and `ID -> count` will have at most N entries. The keys of the first map are short strings whose size is not dependent on N. The recursion stack depth is at most the height of the tree, which is O(N) in the worst case. Thus, the overall space is linear.
**Pros:** Highly efficient with linear time and space complexity.; Avoids performance issues related to long string manipulation and storage.
**Cons:** Slightly more complex to implement due to the use of multiple maps and ID management.
### Explanation
This approach improves upon string serialization by avoiding the creation and storage of long, memory-intensive strings. The core idea is to represent each unique subtree structure with a compact integer ID instead of a full string.

We still use a post-order traversal. For any given node, its structure is uniquely defined by its own value and the structures of its left and right subtrees. So, if we have unique IDs for the left and right subtrees, we can form a composite key, or a 'triplet', like `(node.val, left_subtree_id, right_subtree_id)`. This triplet uniquely represents the structure at the current node.

We use a map (`tripletToId`) to assign a new, incrementing integer ID to each new triplet we encounter. If we see a triplet that's already in the map, we reuse its existing ID. This way, identical subtrees will resolve to the same ID.

We use a second map (`idToCount`) to count the occurrences of each ID. When the count for an ID reaches 2, we've found a duplicate, and we add the current node to our result list. This method reduces the time and space complexity significantly because we are only creating and storing very short strings (for the triplets) and integers.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int nextId;
    private Map<String, Integer> tripletToId;
    private Map<Integer, Integer> idToCount;
    private List<TreeNode> result;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        this.nextId = 1;
        this.tripletToId = new HashMap<>();
        this.idToCount = new HashMap<>();
        this.result = new ArrayList<>();
        
        getOrAssignId(root);
        
        return result;
    }

    private int getOrAssignId(TreeNode node) {
        if (node == null) {
            return 0; // ID for null subtrees
        }
        
        int leftId = getOrAssignId(node.left);
        int rightId = getOrAssignId(node.right);
        
        String triplet = node.val + "," + leftId + "," + rightId;
        
        // Get an ID for this triplet, creating a new one if necessary
        int id = tripletToId.computeIfAbsent(triplet, k -> nextId++);
        
        // Update the count for this ID
        idToCount.put(id, idToCount.getOrDefault(id, 0) + 1);
        
        // If we've just seen this subtree for the second time, add it to the result
        if (idToCount.get(id) == 2) {
            result.add(node);
        }
        
        return id;
    }
}
```
### Algorithm
- Initialize an empty list `result`, a map `tripletToId` to store `(triplet_string -> id)`, a map `idToCount` to store `(id -> count)`, and an integer `nextId = 1`.
- Define a recursive function `getOrAssignId(node)` that returns an integer ID for the subtree.
- Base Case: If `node` is `null`, return `0` (a special ID for null subtrees).
- Recursive Step: Recursively get IDs for left and right children: `leftId = getOrAssignId(node.left)` and `rightId = getOrAssignId(node.right)`.
- Form a triplet string: `triplet = node.val + "," + leftId + "," + rightId`.
- Look for this `triplet` in `tripletToId`. If it's not present, it's a new unique subtree structure. Assign it a new ID: `id = nextId++` and store the mapping `(triplet, id)` in `tripletToId`. Otherwise, get the existing `id`.
- Increment the count for `id` in the `idToCount` map.
- If the count for `id` becomes exactly `2`, add the current `node` to the `result` list.
- Return the `id` for the current subtree.
- Start the process by calling `getOrAssignId(root)`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < String , Integer > counter ; private List < TreeNode > ans ; public List < TreeNode > findDuplicateSubtrees ( TreeNode root ) { counter = new HashMap <>(); ans = new ArrayList <>(); dfs ( root ); return ans ; } private String dfs ( TreeNode root ) { if ( root == null ) { return "#" ; } String v = root . val + "," + dfs ( root . left ) + "," + dfs ( root . right ); counter . put ( v , counter . getOrDefault ( v , 0 ) + 1 ); if ( counter . get ( v ) == 2 ) { ans . add ( root ); } return v ; } }
```

### CPP

```cpp
/** * 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 { public: unordered_map < string , int > counter ; vector < TreeNode *> ans ; vector < TreeNode *> findDuplicateSubtrees ( TreeNode * root ) { dfs ( root ); return ans ; } string dfs ( TreeNode * root ) { if ( ! root ) return "#" ; string v = to_string ( root -> val ) + "," + dfs ( root -> left ) + "," + dfs ( root -> right ); ++ counter [ v ]; if ( counter [ v ] == 2 ) ans . push_back ( root ); return v ; } };
```

### Python

```python
# 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 ]]: def dfs ( root ): if root is None : return '#' v = f ' { root . val } , { dfs ( root . left ) } , { dfs ( root . right ) } ' counter [ v ] += 1 if counter [ v ] == 2 : ans . append ( root ) return v ans = [] counter = Counter () dfs ( root ) return ans
```