Check if a Binary Tree contains duplicate subtrees of size 2 or more

The problem, simply

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

Answer true if the tree has two copies of a subtree with at least 2 nodes. Copies of a single leaf do not count, because a lonely leaf is too small.

A story to remember it

Picture it

Examples

Way 1: the simple way

Compare every pair of subtrees that have at least 2 nodes.

1. Collect every node that has at least one child. Those are the roots of subtrees with 2 or more nodes.
2. For every pair of them, check if the two subtrees are identical, node by node.
3. If any pair matches, answer true.

import java.util.*;

class Solution {
    public boolean hasDuplicate(TreeNode root) {
        List<TreeNode> big = new ArrayList<>();
        collect(root, big);
        for (int i = 0; i < big.size(); i++)
            for (int j = i + 1; j < big.size(); j++)
                if (same(big.get(i), big.get(j))) return true;
        return false;
    }

    private void collect(TreeNode n, List<TreeNode> big) {
        if (n == null) return;
        if (n.left != null || n.right != null) big.add(n);   // has 2 or more nodes
        collect(n.left, big);
        collect(n.right, big);
    }

    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: there are up to n big subtrees, so about n^2 pairs, and comparing a pair can take up to n steps. Worst case O(n^3), for example a long chain where every value is the same. Extra room: the list and the recursion, O(n).

Way 2: the clever way

Do what the teacher does. Visit children before parents, and give every subtree a sticker number that stands for its shape.

1. An empty spot gets sticker 0.
2. For a node, first get the stickers of its left and right subtrees. Its shape is the short note left sticker, value, right sticker.
3. Look the note up in a map. If it is new, hand out the next sticker number.
4. If it is not new and the node has a child, we found a copy of size 2 or more. Answer true.

Because the note uses the children's stickers, two subtrees get the same sticker exactly when they are identical. And each note is only three numbers long, so looking it up is quick.

import java.util.*;

class Solution {
    private Map<String, Integer> sticker = new HashMap<>();
    private boolean found;

    public boolean hasDuplicate(TreeNode root) {
        sticker.clear();
        found = false;
        label(root);
        return found;
    }

    // returns the sticker number for the shape of this subtree
    private int label(TreeNode n) {
        if (n == null || found) return 0;
        int l = label(n.left);
        int r = label(n.right);
        String shape = l + "," + n.val + "," + r;      // children first, then me
        Integer id = sticker.get(shape);
        if (id == null) {
            id = sticker.size() + 1;
            sticker.put(shape, id);
        } else if (n.left != null || n.right != null) {
            found = true;                              // a copy with 2 or more nodes
        }
        return id;
    }
}

How long it takes: every node is visited once and builds a note of three numbers, so O(n). Extra room: the map has at most n notes, O(n).

Watch out for

• Counting leaf copies. Two leaves with the same value are copies of size 1. They must not turn the answer to true.
• Building the whole shape as one long string at every node. It works, but strings can be n long, so it becomes O(n^2) in the worst case. Stickers keep each note short.
• The same node twice. A subtree is not a copy of itself. Each node is counted once in the map, so this cannot happen here.

What interviewers ask next

• Return every duplicate subtree, not just yes or no? Count how many times each sticker appears and save the root when the count hits 2. That is LeetCode 652.
• Is there a smaller check? Yes. If a copy with 2 or more nodes exists, then a copy of a small subtree of height 1 (a node whose children are leaves) also exists, because the deepest non-leaf node in the copy is copied too. So you only need to compare those tiny subtrees.
• Can you do it without any map? Not easily in O(n). Hashing the shapes is the standard tool.
• What about a quick hash instead of stickers? A rolling hash of (left, value, right) is also O(n), but two different shapes can collide, so you would need a check.

Remember this

Grown-up words: the sticker book is a hash map, the stickers are subtree ids, the short notes are serializations, and children before parents is post order traversal.