Find Duplicate Subtrees

LeetCode 652: Find Duplicate Subtrees Solution & Explanation

Problem Overview

TL;DR: Perform a post-order traversal to serialize every subtree into a string representation, storing counts in a hash map to identify duplicates.

The Find Duplicate Subtrees problem asks us to identify all subtrees within a binary tree that appear more than once. A duplicate is defined as a subtree having the exact same structure and node values as another subtree elsewhere in the hierarchy. If multiple instances of a duplicate exist, we only need to return the root node of one of them.

This is a popular interview question (LeetCode 652) because it tests the ability to efficiently represent complex data structures (trees) in a format that allows for rapid comparison (strings or IDs).

Brute Force Approach for Find Duplicate Subtrees

The naive approach involves iterating through every node in the tree and treating it as the root of a candidate subtree. For every candidate, we compare it against every other node's subtree to check for equality.

1. Traverse the tree to visit every node i.
2. For each node i, traverse the rest of the tree to visit every other node j.
3. Call a helper function isSameTree(node_i, node_j) which performs a simultaneous traversal of both subtrees to verify if they are identical.
4. If they are identical, add node_i to the result set (ensuring we don't add the same type of duplicate multiple times).

Why this fails: The time complexity of this approach is prohibitive. Comparing two trees takes $O(N)$ time in the worst case. Since we compare every node against every other node, the nested iteration results in $O(N^2)$ pairs. The total time complexity becomes $O(N^3)$. With $N$ up to 5000, $N^3$ is $125 \times 10^9$ operations, which will inevitably result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Tree - Serialization and Deserialization

We will use a Post-order DFS traversal to generate serializations for every subtree.

1. Global Storage: Maintain a Hash Map (frequency_map) that maps a serialization string to the number of times it has appeared. Also, maintain a list (result) to store the roots of duplicate subtrees.
2. Traversal: Define a recursive function serialize(node):
   • Base Case: If node is null, return a unique marker string (e.g., "#").
   • Recursive Step: Recursively call serialize on the left child and right child to get their string representations.
   • Construction: Form the current subtree's serialization string using the format: node.val + "," + left_serial + "," + right_serial.
3. Registration:
   • Check the frequency_map for the constructed string.
   • Increment the count for this string.
   • Critical Check: If the count becomes exactly 2, it means this is the first time we have identified this subtree as a duplicate. Add node to the result list. We do not add it when the count is 3 or more to avoid duplicates in the output.
4. Return: The function returns the serialization string to the parent caller.

Execution Flow

1. Initialize countMap as an empty hash map and result as an empty list.
2. Call the recursive function traverse(root).
3. Inside Recursion (e.g., at a leaf node with value 4):
   • Left child is null $\rightarrow$ returns "#".
   • Right child is null $\rightarrow$ returns "#".
   • Current serialization becomes "4,#,#".
   • Update countMap: {"4,#,#": 1}.
   • Return "4,#,#" to the parent.
4. At a higher node (e.g., value 2, left child 4):
   • Receive "4,#,#" from the left.
   • Assume right child returns "#".
   • Current serialization becomes "2,4,#,#,#".
   • Update countMap: {"2,4,#,#,#": 1}.
   • Return "2,4,#,#,#" to the parent.
5. Detecting a Duplicate:
   • Later in the tree, we encounter another node with value 4.
   • It generates "4,#,#".
   • We check countMap. The key "4,#,#" exists with count 1.
   • Increment count to 2.
   • Since count is now 2, add this node to result.
6. Finish traversal and return result.

Proof of Correctness

The correctness relies on the unique mapping between a binary tree structure and its serialization string (when nulls are included).

• Uniqueness: Using Pre-order or Post-order traversal including null markers guarantees that distinct tree structures produce distinct strings.
• Completeness: The Post-order traversal visits every node. Therefore, every possible subtree in the original tree is serialized and checked against the map.
• Duplicate Handling: By adding to the result only when the counter transitions from 1 to 2, we ensure that each class of duplicate subtrees is reported exactly once.

Pattern Reuse Notes

The Tree - Serialization and Deserialization pattern is versatile.

• LeetCode 297: Serialize and Deserialize Binary Tree: This is the canonical problem for this pattern. The logic used here to build the string is exactly what is needed for the serialize method in LC 297.
• LeetCode 572: Subtree of Another Tree: While typically solved with recursion, you can also solve this by serializing both trees and checking if the serialization of the smaller tree is a substring of the larger tree (with careful boundary handling).

Reference Implementation

C++ Solution for LeetCode 652

1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5
6using namespace std;
7
8// Definition for a binary tree node.
9struct TreeNode {
10    int val;
11    TreeNode *left;
12    TreeNode *right;
13    TreeNode() : val(0), left(nullptr), right(nullptr) {}
14    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
15    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
16};
17
18class Solution {
19public:
20    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
21        unordered_map<string, int> countMap;
22        vector<TreeNode*> result;
23        serialize(root, countMap, result);
24        return result;
25    }
26
27private:
28    string serialize(TreeNode* node, unordered_map<string, int>& countMap, vector<TreeNode*>& result) {
29        if (!node) {
30            return "#";
31        }
32
33        // Post-order traversal: Left, Right, Root
34        string leftSerial = serialize(node->left, countMap, result);
35        string rightSerial = serialize(node->right, countMap, result);
36
37        // Construct unique key for the current subtree
38        string serial = to_string(node->val) + "," + leftSerial + "," + rightSerial;
39
40        // Update map and check for duplicates
41        countMap[serial]++;
42        
43        if (countMap[serial] == 2) {
44            result.push_back(node);
45        }
46
47        return serial;
48    }
49};

Java Solution for LeetCode 652

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6// Definition for a binary tree node.
7class TreeNode {
8    int val;
9    TreeNode left;
10    TreeNode right;
11    TreeNode() {}
12    TreeNode(int val) { this.val = val; }
13    TreeNode(int val, TreeNode left, TreeNode right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
22        Map<String, Integer> countMap = new HashMap<>();
23        List<TreeNode> result = new ArrayList<>();
24        serialize(root, countMap, result);
25        return result;
26    }
27
28    private String serialize(TreeNode node, Map<String, Integer> countMap, List<TreeNode> result) {
29        if (node == null) {
30            return "#";
31        }
32
33        // Post-order traversal to build string from bottom up
34        String leftSerial = serialize(node.left, countMap, result);
35        String rightSerial = serialize(node.right, countMap, result);
36
37        // Construct serialization key
38        // Using explicit concatenation for clarity; StringBuilder is also valid
39        String serial = node.val + "," + leftSerial + "," + rightSerial;
40
41        countMap.put(serial, countMap.getOrDefault(serial, 0) + 1);
42
43        // Only add to result the first time we detect a duplicate
44        if (countMap.get(serial) == 2) {
45            result.add(node);
46        }
47
48        return serial;
49    }
50}

Python Solution for LeetCode 652

1from typing import Optional, List
2from collections import defaultdict
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
13        count_map = defaultdict(int)
14        result = []
15
16        def serialize(node):
17            if not node:
18                return "#"
19            
20            # Post-order traversal
21            left_serial = serialize(node.left)
22            right_serial = serialize(node.right)
23            
24            # Create unique signature for the subtree
25            serial = f"{node.val},{left_serial},{right_serial}"
26            
27            count_map[serial] += 1
28            
29            # If this is the second time we've seen this signature, it's a duplicate
30            if count_map[serial] == 2:
31                result.append(node)
32                
33            return serial
34
35        serialize(root)
36        return result