Last updated on February 12th, 2025 at 02:30 am

Here, we see a Find Duplicate Subtrees LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Tree

Companies

Google

Level of Question

Medium

Find Duplicate Subtrees LeetCode Solution

1. 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:

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

Example 2:

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

Example 3:

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

2. Coding Pattern Used in Solution

The coding pattern used in this code is Tree Depth First Search (DFS). The code traverses the binary tree using a recursive DFS approach to serialize each subtree and identify duplicate subtrees. The serialization of subtrees is stored in a hash map (or dictionary) to track their frequency, and duplicate subtrees are added to the result list.

3. Code Implementation in Different Languages

3.1 Find Duplicate Subtrees C++

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int>m;
        vector<TreeNode*>res;
        DFS(root, m, res);
        return res;
    }
    string DFS(TreeNode* root, unordered_map<string, int>& m, vector<TreeNode*>& res){
        if(!root) return "";
        string s = to_string(root->val) + "," + DFS(root->left, m, res) + "," + DFS(root->right, m, res);
        if(m[s]++ == 1) res.push_back(root);
        return s;
    }
};

3.2 Find Duplicate Subtrees Java

class Solution 
{
    HashMap<String, Integer> map= new HashMap<>();
    ArrayList<TreeNode> res= new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) 
    {
        Mapper(root);
        return res;
    }
    public String Mapper(TreeNode root)
    {
        if(root == null)
            return "N";
        String left= Mapper(root.left);
        String right= Mapper(root.right);
        String curr= root.val +" "+left +" "+ right;
        map.put(curr, map.getOrDefault(curr, 0)+ 1);
        if(map.get(curr) == 2)
            res.add(root);
        return curr;
    }
}

3.3 Find Duplicate Subtrees JavaScript

var findDuplicateSubtrees = function(root) {
  const map = new Map(), res = []
  dfs(root, map, res)
  return res
};
function dfs(root, map, res){
  if(!root) return '#'
  const subtree = `${root.val}.${dfs(root.left,map,res)}.${dfs(root.right, map,res)}`
  map.set(subtree,(map.get(subtree)||0) + 1)
  if(map.get(subtree) === 2){
    res.push(root)
  }
  return subtree
}

3.4 Find Duplicate Subtrees Python

class Solution(object):
    def findDuplicateSubtrees(self, root):
        res = []
        hmap = {}
        def recurse(node, path):
            if node is None:
                return '#'
            path += ','.join([str(node.val), recurse(node.left, path), recurse(node.right, path)])
            if path in hmap:
                hmap[path] += 1
                if hmap[path] == 2:
                    res.append(node)
            else:
                hmap[path] = 1
            return path
        recurse(root, '')
        return res

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n²)	O(n²)
Java	O(n²)	O(n²)
JavaScript	O(n²)	O(n²)
Python	O(n²)	O(n²)

The time complexity is dominated by the serialization process, which depends on the height of the tree.
The space complexity is influenced by the hash map and the recursive call stack.
The implementation is efficient for balanced trees but can degrade for skewed trees due to the height (h) approaching (n).