Find all Duplicate subtrees in a Binary tree

The problem, simply

You get a binary tree. A subtree is a node with everything below it. Two subtrees are duplicates if they have the same shape and the same values in the same places.

Return the root of one copy for every kind of subtree that appears at least twice. Each kind is reported once, even if it appears three or more times, and the order of the answer does not matter. Single leaves count here.

A story to remember it

Picture it

Examples

Way 1: the simple way

Compare every node's subtree with every other node's subtree.

1. Collect all nodes.
2. For each node, skip it if a copy of it is already in the answer.
3. Otherwise compare it with every later node. If one is identical, add this node to the answer.

import java.util.*;

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> all = new ArrayList<>();
        collect(root, all);
        List<TreeNode> out = new ArrayList<>();
        for (int i = 0; i < all.size(); i++) {
            TreeNode a = all.get(i);
            boolean reported = false;
            for (TreeNode r : out) if (same(r, a)) { reported = true; break; }
            if (reported) continue;                       // this kind is already listed
            for (int j = i + 1; j < all.size(); j++) {
                if (same(a, all.get(j))) { out.add(a); break; }
            }
        }
        return out;
    }

    private void collect(TreeNode n, List<TreeNode> all) {
        if (n == null) return;
        all.add(n);
        collect(n.left, all);
        collect(n.right, all);
    }

    private boolean same(TreeNode x, TreeNode y) {
        if (x == null && y == null) return true;
        if (x == null || y == null) return false;
        return x.val == y.val && same(x.left, y.left) && same(x.right, y.right);
    }
}

How long it takes: about n^2 pairs, and each comparison can take up to n steps, so O(n^3) in the worst case. Extra room: the list of nodes, O(n).

Way 2: the clever way

Use the sticker book. Visit children before parents, so a node can describe itself with its children's stickers.

1. An empty spot has sticker 0.
2. A node's shape is the short note left sticker, value, right sticker.
3. If the note is new, give it the next sticker number.
4. Add 1 to that sticker's tally. If the tally just became 2, add this node to the answer.

Two subtrees get the same sticker exactly when they are identical, because their children got the same stickers first. Each note is just three numbers, so it is quick to build and look up.

import java.util.*;

class Solution {
    private Map<String, Integer> sticker = new HashMap<>();   // shape -> sticker number
    private Map<Integer, Integer> tally = new HashMap<>();    // sticker -> times seen
    private List<TreeNode> out = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        sticker.clear();
        tally.clear();
        out = new ArrayList<>();
        label(root);
        return out;
    }

    private int label(TreeNode n) {
        if (n == null) return 0;
        int l = label(n.left);
        int r = label(n.right);
        String shape = l + "," + n.val + "," + r;
        Integer id = sticker.get(shape);
        if (id == null) {
            id = sticker.size() + 1;
            sticker.put(shape, id);
        }
        int seen = tally.merge(id, 1, Integer::sum);
        if (seen == 2) out.add(n);            // first repeat: report it once
        return id;
    }
}

How long it takes: every node builds one short note and does two map lookups, O(n). Extra room: two maps with at most n entries, O(n).

Another way: write each shape as a string

Many people describe each subtree with its whole shape as one string, like "4,#,#" for a leaf and "2,4,#,#,#" for 2 over 4, and count the strings. It is easy to write and fine in an interview, but say the cost: the strings get as long as the subtree, so building and hashing them costs O(n^2) in the worst case.

import java.util.*;

class Solution {
    private Map<String, Integer> count = new HashMap<>();
    private List<TreeNode> out = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        count.clear();
        out = new ArrayList<>();
        write(root);
        return out;
    }

    private String write(TreeNode n) {
        if (n == null) return "#";
        String s = n.val + "," + write(n.left) + "," + write(n.right);   // preorder with markers
        if (count.merge(s, 1, Integer::sum) == 2) out.add(n);
        return s;
    }
}

Watch out for

• Notes without markers for empty children. Then a child on the left and a child on the right look the same, as in the fourth example.
• Notes without separators. 1 and 23 glued together look like 12 and 3.
• Inorder strings fail even with null markers: a 0 with a left child 0 and a 0 with a right child 0 both write #,0,#,0,#. Use preorder or postorder with null markers, or the sticker trick.

What interviewers ask next

• Only yes or no, and only for subtrees with at least 2 nodes? Stop at the first repeat on a node that has a child. See "Check if a binary tree contains duplicate subtrees of size 2 or more".
• Why are stickers O(n) but strings O(n^2)? A sticker note always has three parts, while a string repeats the whole subtree. A long chain makes strings of length 1, 2, 3, up to n.
• Count how many times each duplicate appears? Return the tallies along with the roots.
• Could you use a numeric hash instead of a map of notes? Yes, a hash of (left, value, right) works in O(n), but different shapes can collide, so you need a way to break ties.

Remember this

Grown-up words: the sticker book is a hash map from serialization to id, the stickers are subtree ids, the tally is a frequency count, and children before parents is post order traversal.