algoadvance

Leetcode 652. Find Duplicate Subtrees

Problem Statement

Given the root of a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are considered duplicate if they have the same structure with the same node values.

Example 1:

         1
        / \
       2   3
      /   / \
     4   2   4
        /
       4

Output:

[
  [2,4],
  [4]
]

Example 2:

         2
        / \
       1   1

Output:

[
  [1]
]

Clarifying Questions

1. What is the definition of a “subtree”?
   • A subtree is a portion of a tree consisting of a node and all its descendants.
2. How should the result be returned/outputted?
   • The result should be returned as a list of TreeNode objects, each representing the root node of a duplicate subtree.
3. What is the range of input sizes?
   • There are no strict limitations given in the problem, but typically binary trees with up to a few thousand nodes are a reasonable assumption.
4. Does the tree have any constraints related to balancing?
   • It’s a general binary tree and does not necessarily have any balance constraints.

Strategy

1. Serialization of Subtrees: Traverse the tree and serialize each subtree (using post-order traversal to serialize the entire subtree starting from the bottom).
2. Hashmap for Frequency Counting: Use a hashmap to record the frequency of each serialized subtree.
3. List for Results: If a serialized subtree appears more than once, add the root node of the first instance of this subtree to the result list.
4. Identify Duplicates: Return all root nodes of duplicate subtrees.

The serialization can be done by encoding each subtree into a string in a way that considers both node values and structure.

Code

Here is the Java implementation of the proposed strategy:

import java.util.*;
import javafx.util.*;

public class Solution {
    private Map<String, Integer> count;
    private List<TreeNode> result;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        count = new HashMap<>();
        result = new ArrayList<>();
        serialize(root);
        return result;
    }

    private String serialize(TreeNode node) {
        if (node == null) {
            return "#"; // A marker for null nodes
        }
        String serial = node.val + "," + serialize(node.left) + "," + serialize(node.right);
        count.put(serial, count.getOrDefault(serial, 0) + 1);
        if (count.get(serial) == 2) {
            result.add(node);
        }
        return serial;
    }

    // Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

Explanation

• Serialization: Each node is serialized into a string representing its value and the structure of its left and right subtrees. This is done recursively.

• Hashmap (count): The serialized form is used as the key in the hashmap, and the value is the count of how many times this form has been seen.

• Result List: When serialization of a subtree is encountered for the second time (count.get(serial) == 2), the root of this subtree is added to the result list.

Time Complexity

The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited once, and serialization of each subtree is linear in the size of the subtree.

• Space Complexity: Also O(n) for the storage used by the hashmap and result list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?