Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Find Duplicate Subtrees

Try it yourself
MediumProblemExternal link

Description

Given the root of a binary tree, return all the subtrees that appear more than once.

Two subtrees are duplicates when they have the same shape and the same value in every node. For each kind of duplicate, return the root node of any one copy. The answer can be in any order.

A subtree is a node together with everything below it. In the examples, each subtree in the output is written as LeetCode's list.

Examples

Example 1

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

Output: [[2,4],[4]]

Explanation: The leaf 4 appears three times and the subtree 2 → 4 twice; each is returned once.

Example 2

Input: root = [2, 1, 1]

Output: [[1]]

Explanation: The two leaves 1 are the same subtree.

Example 3

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

Output: [[2,3],[3]]

Explanation: The subtree 2 with a left child 3 appears twice, and so does the leaf 3. The whole tree appears once.

Constraints

  • The number of nodes in the tree is in the range [1, 5000].
  • −200 ≤ Node.val ≤ 200

Editorial

Brute Force

Intuition

Write each subtree out in a way that fixes the tree, and two subtrees are duplicates exactly when they read the same. Preorder with a # for every missing child does that: the marks say where each subtree ends, so no two different trees read the same. Write every subtree out like that, children first so each text is built from its children's, and count the texts in a hash map. The second time a text appears, report the node.

Step-by-Step Explanation

Let's trace root = [1, 2, 3, 4, null, 2, 4, null, null, 4]:

  1. 4 reads 4,#,#, new.
  2. 2 reads 2,4,#,#,#, new.
  3. 4 reads 4,#,#, the second time that text appears, so 4 is reported.
  4. 2 reads 2,4,#,#,#, the second time that text appears, so 2 is reported.
  5. 4 reads 4,#,#, seen 3 times now; it's already reported.
  6. 3 reads 3,2,4,#,#,#,4,#,#, new.
  7. 1 reads 1,2,4,#,#,#,3,2,4,#,#,#,4,#,#, new.

Every Subtree, Written Out — Indigo is the node being written; violet, the subtrees written; green, the ones reported.

Algorithm

  1. write(node): return # for an empty child. Otherwise build val,left,right from both children's texts, add 1 to its count, and when the count reaches 2, add node to the answer.
  2. Call write(root) and return the answer.

Code

class Solution {
    unordered_map<string, int> count;     // each subtree's text -> how many subtrees read that way
    vector<TreeNode*> found;

    // the whole subtree in preorder, with '#' for every missing child
    string write(TreeNode* node) {
        if (node == nullptr) return "#";
        string text = to_string(node->val) + "," + write(node->left) + "," + write(node->right);
        if (++count[text] == 2) found.push_back(node);   // its second appearance: report it, once
        return text;
    }

public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        write(root);
        return found;
    }
};

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        count, found = {}, []             # each subtree's text -> how many subtrees read that way

        def write(node):                  # the whole subtree in preorder, with '#' for every missing child
            if node is None:
                return "#"
            text = f"{node.val},{write(node.left)},{write(node.right)}"
            count[text] = count.get(text, 0) + 1
            if count[text] == 2:          # its second appearance: report it, once
                found.append(node)
            return text

        write(root)
        return found

class Solution {
    private final Map<String, Integer> count = new HashMap<>();   // each subtree's text -> how many read that way
    private final List<TreeNode> found = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        write(root);
        return found;
    }

    // the whole subtree in preorder, with '#' for every missing child
    private String write(TreeNode node) {
        if (node == null) return "#";
        String text = node.val + "," + write(node.left) + "," + write(node.right);
        if (count.merge(text, 1, Integer::sum) == 2) found.add(node);   // its second appearance: report it, once
        return text;
    }
}

var findDuplicateSubtrees = function(root) {
    const count = new Map();              // each subtree's text -> how many subtrees read that way
    const found = [];
    const write = (node) => {             // the whole subtree in preorder, with '#' for every missing child
        if (node === null) return "#";
        const text = `${node.val},${write(node.left)},${write(node.right)}`;
        count.set(text, (count.get(text) || 0) + 1);
        if (count.get(text) === 2) found.push(node);   // its second appearance: report it, once
        return text;
    };
    write(root);
    return found;
};

Complexity Analysis

Time Complexity: O(n²)

Each node's text holds its whole subtree, so on a chain the texts add up to about n²/2 values, and each is built and hashed.

Space Complexity: O(n²)

The map keeps every text.

Why This Approach Is Not Efficient

It passes here, in every language, but it writes the same values over and over. On a chain of 5,000 equal values, the tests' deepest tree, the texts added up to 50,015,000 characters and took 61.9 ms in Python, against 4.51 ms for the ids below.

A text repeats its children's texts in full. But once a child's shape has been seen, a short name for it is enough: give every shape a number the first time it appears. Then a node's shape is just three numbers, its left child's id, its value and its right child's id, and two nodes have the same shape exactly when those three numbers match.

Optimal Approach - An Id for Every Shape

Intuition

Visit the children first, so both have ids when their parent is reached. The empty subtree is id 0.

  • The key: (left id, value, right id). Equal keys mean equal subtrees: the same value on top, and children of the same shapes.
  • The id: a key not seen before gets the next number; a key seen before gets its old one.
  • The count: when an id is seen the second time, report the node, once.

Step-by-Step Explanation

Let's trace root = [1, 2, 3, 4, null, 2, 4, null, null, 4]:

  1. 4's key is (0, 4, 0), not seen before, so it gets id 1.
  2. 2's key is (1, 2, 0), not seen before, so it gets id 2.
  3. 4's key is (0, 4, 0), already id 1, and this is its second appearance, so 4 is reported.
  4. 2's key is (1, 2, 0), already id 2, and this is its second appearance, so 2 is reported.
  5. 4's key is (0, 4, 0), id 1 again, seen 3 times; it's already reported.
  6. 3's key is (2, 3, 1), not seen before, so it gets id 3.
  7. 1's key is (2, 1, 3), not seen before, so it gets id 4.

An Id for Every Shape — The badge on each node is its shape's id. Indigo is the node being named; green, the ones reported.

Algorithm

  1. shape(node): return 0 for an empty child. Otherwise make the key (shape(node.left), node.val, shape(node.right)), give it the next id if it's new, and add 1 to that id's count; when the count reaches 2, add node to the answer. Return the id.
  2. Call shape(root) and return the answer.

Code

class Solution {
    map<tuple<int, int, int>, int> ids;   // (left id, value, right id) -> the id of that shape
    unordered_map<int, int> count;        // id -> how many subtrees have that shape
    vector<TreeNode*> found;

    int shape(TreeNode* node) {
        if (node == nullptr) return 0;    // the empty subtree
        tuple<int, int, int> key{shape(node->left), node->val, shape(node->right)};
        auto it = ids.find(key);
        int sid;
        if (it != ids.end()) {
            sid = it->second;
        } else {
            sid = (int)ids.size() + 1;    // a shape not seen before gets the next id
            ids[key] = sid;
        }
        if (++count[sid] == 2) found.push_back(node);   // its second appearance: report it, once
        return sid;
    }

public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        shape(root);
        return found;
    }
};

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        ids = {}                          # (left id, value, right id) -> the id of that shape
        count = {}                        # id -> how many subtrees have that shape
        found = []

        def shape(node):
            if node is None:
                return 0                  # the empty subtree
            key = (shape(node.left), node.val, shape(node.right))
            if key not in ids:
                ids[key] = len(ids) + 1
            sid = ids[key]
            count[sid] = count.get(sid, 0) + 1
            if count[sid] == 2:           # its second appearance: report it, once
                found.append(node)
            return sid

        shape(root)
        return found

class Solution {
    private final Map<String, Integer> ids = new HashMap<>();   // "left id,value,right id" -> the id of that shape
    private final Map<Integer, Integer> count = new HashMap<>(); // id -> how many subtrees have that shape
    private final List<TreeNode> found = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        shape(root);
        return found;
    }

    private int shape(TreeNode node) {
        if (node == null) return 0;                              // the empty subtree
        String key = shape(node.left) + "," + node.val + "," + shape(node.right);
        int sid = ids.computeIfAbsent(key, k -> ids.size() + 1);
        if (count.merge(sid, 1, Integer::sum) == 2) found.add(node);   // its second appearance: report it, once
        return sid;
    }
}

var findDuplicateSubtrees = function(root) {
    const ids = new Map();                // "left id,value,right id" -> the id of that shape
    const count = new Map();              // id -> how many subtrees have that shape
    const found = [];
    const shape = (node) => {
        if (node === null) return 0;      // the empty subtree
        const key = `${shape(node.left)},${node.val},${shape(node.right)}`;
        if (!ids.has(key)) ids.set(key, ids.size + 1);
        const sid = ids.get(key);
        count.set(sid, (count.get(sid) || 0) + 1);
        if (count.get(sid) === 2) found.push(node);   // its second appearance: report it, once
        return sid;
    };
    shape(root);
    return found;
};

Complexity Analysis

Time Complexity: O(n)

Each node makes one key of three numbers and does one lookup (C++'s ordered map makes that O(log n) each, still fast).

Space Complexity: O(n)

An id and a count for each shape, and the recursion, as deep as the tree.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code, each list sorted.

Leaving out the marks for missing children. parts = [str(node.val)] + [p for p in (write(node.left), write(node.right)) if p]

On root = [1, 1, 1, 1, null, null, 1] it returns [[1,null,1],[1]]; the answer is [[1]]. Without a mark for each missing child, a 1 with a left child 1 and a 1 with a right child 1 are both written 1,1, and two different shapes look like one. Every missing child needs its mark.

Writing the subtree in inorder. key = write(node.left) + "," + str(node.val) + "," + write(node.right)

On root = [3, 1, 2, null, 2, 1] it returns [[2,1]]; the answer is []. Inorder puts the node between its subtrees, and even with marks that's ambiguous: a 1 with a right child 2 and a 2 with a left child 1 both read #,1,#,2,#. Preorder or postorder with marks fixes a tree; inorder doesn't.

Reporting every repeat. if count[sid] >= 2:

On root = [0, 0, 0, 0, 0, 0, 0] it returns [[0,0,0],[0],[0],[0]]; the answer is [[0,0,0],[0]]. Each duplicated subtree is reported once. Adding the node every time its shape is seen again, >= 2 instead of == 2, reports the same leaf three times when it appears four times.

Where This Pattern Is Taught

This problem practises recursion that returns a value up the tree. It's taught in Recursion on Trees: Heights, Paths and Return Values, which measures the texts against the ids, and in Building and Serializing Trees, which shows why the marks for missing children make one list enough.