Duplicate Subtrees

JavaView on GFG

Time: O(n^2)

Space: O(n^2)

Intuition

Serialize each subtree to a string. Use a frequency map; when a serialization is seen twice, add the root to result.

Algorithm

1Post-order DFS: serialize = left_serial + "," + right_serial + "," + root.val.
2Map of serialization -> count. If count becomes 2: add root to result.

Common Pitfalls

•Add to result only when count == 2 (not 3,4,...) to avoid duplicates in output.

Duplicate Subtrees.java

Java

// Approach: Serialize each subtree to a string. Use a HashMap to count; collect subtrees with count >= 2.
// Time: O(n^2) Space: O(n^2)
import java.util.*;

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
    }
}

class Solution {
    public List<Node> printAllDups(Node root) {
        HashMap<String, Integer> map = new HashMap<>();
        List<Node> l = new ArrayList<>();

        solve(root, l, map);

        Collections.sort(l, (a, b) -> a.data - b.data);

        return l;
    }

    private String solve(Node root, List<Node> l, HashMap<String, Integer> map) {
        if (root == null)
            return "";

        String left = solve(root.left, l, map);
        String right = solve(root.right, l, map);

        String curr = left + "-" + root.data + "-" + right;

        if (map.getOrDefault(curr, 0) == 1)
            l.add(root);

        map.put(curr, map.getOrDefault(curr, 0) + 1);

        return curr;
    }
}

Was this solution helpful?