652. Find Duplicate Subtrees LeetCode Solution

In this guide, you will get 652. Find Duplicate Subtrees LeetCode Solution with the best time and space complexity. The solution to Find Duplicate Subtrees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find Duplicate Subtrees solution in C++
4. Find Duplicate Subtrees solution in Java
5. Find Duplicate Subtrees solution in Python
6. Additional Resources

Problem Statement of Find Duplicate Subtrees

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 duplicate if they have the same structure with the same node values.

Example 1:

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

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

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

Constraints:

The number of the nodes in the tree will be in the range [1, 5000]
-200 <= Node.val <= 200

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

652. Find Duplicate Subtrees LeetCode Solution in C++

class Solution {
 public:
  vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    vector<TreeNode*> ans;
    unordered_map<string, int> count;
    encode(root, count, ans);
    return ans;
  }

 private:
  string encode(TreeNode* root, unordered_map<string, int>& count,
                vector<TreeNode*>& ans) {
    if (root == nullptr)
      return "";

    const string encoded = to_string(root->val) + "#" +
                           encode(root->left, count, ans) + "#" +
                           encode(root->right, count, ans);
    if (++count[encoded] == 2)
      ans.push_back(root);
    return encoded;
  }
};
/* code provided by PROGIEZ */

652. Find Duplicate Subtrees LeetCode Solution in Java

class Solution {
  public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    List<TreeNode> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();
    encode(root, count, ans);
    return ans;
  }

  private String encode(TreeNode root, Map<String, Integer> count, List<TreeNode> ans) {
    if (root == null)
      return "";

    final String encoded =
        root.val + "#" + encode(root.left, count, ans) + "#" + encode(root.right, count, ans);
    if (count.merge(encoded, 1, Integer::sum) == 2)
      ans.add(root);
    return encoded;
  }
}
// code provided by PROGIEZ

652. Find Duplicate Subtrees LeetCode Solution in Python

class Solution:
  def findDuplicateSubtrees(self, root: TreeNode | None) -> list[TreeNode | None]:
    ans = []
    count = collections.Counter()

    def encode(root: TreeNode | None) -> str:
      if not root:
        return ''

      encoded = (str(root.val) + '#' +
                 encode(root.left) + '#' +
                 encode(root.right))
      count[encoded] += 1
      if count[encoded] == 2:
        ans.append(root)
      return encoded

    encode(root)
    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.