LeetCode 652: Find Duplicate Subtrees Solution

Master LeetCode problem 652 (Find Duplicate Subtrees), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

652. Find Duplicate Subtrees

Medium

Hash Table Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a depth-first traversal of the binary tree while keeping track of the subtrees we have encountered. We can use a hashmap to store the subtree strings as keys and their corresponding root nodes as values. As we traverse the tree, we serialize each subtree into a unique string representation to check for duplicates.

Algorithm:

Initialize a hashmap to store the subtree strings and their corresponding root nodes.
Perform a depth-first traversal of the binary tree.
For each subtree encountered:
- Serialize the subtree into a unique string representation.
- Check if the serialized string already exists in the hashmap.
  - If it does, add the root node of the current subtree to the result list.
  - If it doesn't, store the serialized string in the hashmap with the root node as the value.
Return the list of duplicate subtrees.

Time Complexity:

The time complexity of this algorithm is O(n^2) in the worst case, where n is the number of nodes in the binary tree. This is because for each node, we need to serialize the subtree, which takes O(n) time, and we perform this for each node.

Space Complexity:

The space complexity of this algorithm is O(n^2) in the worst case. This is because we store the serialized strings of all subtrees in the hashmap, which can take up to O(n^2) space.

Solution Code

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        Map<String, Integer> count = new HashMap<>();
        Map<TreeNode, String> map = new HashMap<>();
        serialize(root, map, count, result);
        return result;
    }
    
    private String serialize(TreeNode node, Map<TreeNode, String> map, Map<String, Integer> count, List<TreeNode> result) {
        if (node == null) {
            return "#";
        }
        String serial = node.val + "," + serialize(node.left, map, count, result) + "," + serialize(node.right, map, count, result);
        map.put(node, serial);
        count.put(serial, count.getOrDefault(serial, 0) + 1);
        if (count.get(serial) == 2) {
            result.add(node);
        }
        return serial;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 652 (Find Duplicate Subtrees)?

This page provides optimized solutions for LeetCode problem 652 (Find Duplicate Subtrees) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 652 (Find Duplicate Subtrees)?

The time complexity for LeetCode 652 (Find Duplicate Subtrees) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 652 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 652 in Java, C++, or Python.

Back to LeetCode Solutions