Solution For Find Duplicate Subtrees

The Find Duplicate Subtrees problem on LeetCode is a Tree problem that requires you to find and return all duplicate subtrees in a binary tree. In this problem, you are given a binary tree, and you are required to return a list of all the duplicate subtrees. A duplicate subtree is a subtree that appears in the original tree at least twice.

Problem Statement

Given the root of a binary tree, return all duplicate subtrees. For each duplicate subtree, 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

Input:

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

Output:

[2, 4]

Explanation:

There are two duplicate sub-trees:

2
/
4

and

4

Approach

To solve this problem, we can traverse the binary tree in a postorder fashion and store the subtree structure and the frequency of the subtree in a map. We can use a string representation of the subtree structure as the key and a count of the number of times the subtree appears as the value.

We can then traverse the map and find all the duplicate subtrees by checking the frequency of each subtree. Once we find duplicate subtrees, we can add them to a list and return it at the end.

Algorithm

1. Initialize an empty map subtreeCount.
2. Initialize an empty list duplicateSubtrees.
3. Traverse the binary tree in a postorder fashion.
4. For each node in the binary tree, do the following:
5. If the node is a leaf node, return an empty string.
6. Get the string representation of the left subtree of the current node.
7. Get the string representation of the right subtree of the current node.
8. Get the string representation of the current node’s subtree as left_rigth_current.
9. Increment the frequency of the left_right_current subtree in the subtreeCount map.
10. Traverse the subtreeCount map.
11. For each entry in the subtreeCount map, if the frequency of the subtree is greater than 1:
12. Add the root node of the subtree to the duplicateSubtrees list.
13. Return the duplicateSubtrees list.

Complexity Analysis

• Time Complexity: O(n^2), where n is the number of nodes in the binary tree. In the worst-case scenario, we may have to visit each node twice, once to calculate the string representation of the subtree and once to update the subtreeCount map.
• Space Complexity: O(n), where n is the number of nodes in the binary tree. We are using a map subtreeCount to store the frequency of each subtree. In the worst-case scenario, we may have to store all the subtrees in the map, which would require O(n) space.

Code

Here’s the Python code for the above approach:

python
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
def postorder(node):
if not node:
return "#"
left = postorder(node.left)
right = postorder(node.right)
subtree = f"{left},{right},{node.val}"
subtreeCount[subtree] += 1
if subtreeCount[subtree] == 2:
duplicateSubtrees.append(node)
return subtree
subtreeCount = collections.defaultdict(int)
duplicateSubtrees = [] postorder(root)
return duplicateSubtrees

Step by Step Implementation For Find Duplicate Subtrees

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List findDuplicateSubtrees(TreeNode root) {
        List list = new ArrayList<>();
        if(root==null)
            return list;
        Map map = new HashMap<>();
        inorder(root, map, list);
        return list;
    }
    
    public void inorder(TreeNode root, Map map, List list){
        if(root==null)
            return ;
        StringBuffer sb = new StringBuffer();
        sb.append(root.val);
        sb.append(",");
        inorder(root.left, map, list);
        sb.append(inorder(root.right, map, list));
        String str = sb.toString();
        if(map.containsKey(str)){
            if(map.get(str)==1)
                list.add(root);
        }
        else
            map.put(str, 1);
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        # initialize a dictionary to store values of subtrees
        dic = collections.defaultdict(int)
        # initialize a list to store duplicate subtrees
        output = []
        
        # define a helper function to get values of subtrees
        def get_val(node):
            # if node is None, return "#"
            if not node:
                return "#"
            # concatenate values of node.val, left subtree and right subtree
            # and store it in the dictionary
            tree_val = str(node.val) + get_val(node.left) + get_val(node.right)
            # if the value is already in the dictionary, increment the count
            if tree_val in dic:
                dic[tree_val] += 1
            # if the value is not in the dictionary, add it to the dictionary
            else:
                dic[tree_val] = 1
            # return the value of the subtree
            return tree_val
        
        # call the helper function on the root node
        get_val(root)
        # iterate through the dictionary
        for key, val in dic.items():
            # if the value is greater than 1, it is a duplicate subtree
            if val > 1:
                # append the key to the output list
                output.append(key)
        # return the output list

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function(root) {
    
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector findDuplicateSubtrees(TreeNode* root) {
        unordered_map m;
        vector v;
        serialize(root,m,v);
        return v;
    }
    string serialize(TreeNode* root,unordered_map &m,vector &v)
    {
        if(root==NULL)
            return "#";
        string s=to_string(root->val)+","+serialize(root->left,m,v)+","+serialize(root->right,m,v);
        if(++m[s]==2)
            v.push_back(root);
        return s;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList FindDuplicateSubtrees(TreeNode root) {
        
        //Create a list to store all of the duplicate subtrees
        IList duplicates = new List();
        
        //Create a dictionary to store all of the subtrees we have seen
        //The key will be the string representation of the tree
        //The value will be the number of times we have seen that tree
        Dictionary seen = new Dictionary();
        
        //Helper function to get the string representation of a tree
        string getTreeString(TreeNode root)
        {
            //If the tree is null, return the string "null"
            if(root == null)
            {
                return "null";
            }
            
            //Otherwise, return the string representation of the tree
            //This will be the value of the root node, followed by the string representations
            //of the left and right subtrees
            return root.val.ToString() + "," + getTreeString(root.left) + "," + getTreeString(root.right);
        }
        
        //Helper function to add a tree to our dictionary
        void addToSeen(TreeNode root)
        {
            //Get the string representation of the tree
            string treeString = getTreeString(root);
            
            //If we have not seen this tree before, add it to the dictionary with a count of 1
            if(!seen.ContainsKey(treeString))
            {
                seen.Add(treeString, 1);
            }
            //Otherwise, increment the count for this tree
            else
            {
                seen[treeString]++;
            }
        }
        
        //Helper function to check if a tree is a duplicate
        bool isDuplicate(TreeNode root)
        {
            //Get the string representation of the tree
            string treeString = getTreeString(root);
            
            //If we have seen this tree before, and its count is greater than 1, it is a duplicate
            return seen.ContainsKey(treeString) && seen[treeString] > 1;
        }
        
        //Add the root node to our dictionary
        addToSeen(root);
        
        //If the root node is a duplicate, add it to our list
        if(isDuplicate(root))
        {
            duplicates.Add(root);
        }
        
        //Recursively check the left and right subtrees
        if(root.left != null)
        {
            if(isDuplicate(root.left))
            {
                duplicates.Add(root.left);
            }
        }
        if(root.right != null)
        {
            if(isDuplicate(root.right))
            {
                duplicates.Add(root.right);
            }
        }
        
        //Return the list of duplicate subtrees
        return duplicates;
    }
}