Find Duplicate Subtrees (Leetcode - 652) - (GOOGLE) : Explanation ➕ Live Coding
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- This is the 21st Video of our Binary Tree Playlist.
In this video we will try to solve a very interesting problem asked by Google "Find Duplicate Subtrees".
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Find Duplicate Subtrees
Company Tags : GOOGLE
My Github Solutions : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
Great explanation bhai
Below is the java code for your algorithm-:
class Solution {
public List findDuplicateSubtrees(TreeNode root) {
List res = new ArrayList();
Map map = new HashMap();
dfs(map, root, res);
return res;
}
private String dfs(Map map, TreeNode root, List res){
if(root == null)
return "N";
String s = String.valueOf(root.val) + "," + dfs(map, root.left, res) + "," + dfs(map, root.right, res);
if(map.containsKey(s) && map.get(s) == 1)
res.add(root);
map.put(s, map.getOrDefault(s, 0) + 1);
return s;
}
}
If this helps anyone. Overall algorithm is the same but implementation is slightly different.
class Solution {
public List findDuplicateSubtrees(TreeNode root) {
List res = new ArrayList();
HashMap map = new HashMap();
String dummy = dfs(root, map);
for(String key : map.keySet()){
List ls = map.get(key);
if(ls.size() > 1){
res.add(ls.get(0));
}
}
return res;
}
public String dfs(TreeNode root, HashMap map){
if(root == null){
return "null";
}
String key = root.val + "," + dfs(root.left, map) + "," + dfs(root.right, map);
if(map.containsKey(key)){
List temp = map.get(key);
temp.add(root);
map.put(key, temp);
}
else{
List ls = new ArrayList();
ls.add(root);
map.put(key, ls);
}
return key;
}
}
TO think about the approach is next to impossible , if you have not solved such problem before.....
moreover it feels to me like a SMART_TRICK....which you should note down in your copy.........
IF YOU AGREE WITH ME THEN DO UPVOTE :-).....
Yes ur right , If u dont know this problem solution , U just dont know , Practice more problems and playing on probability in interviews is the only way.
Perfectly Explained, with nice and easy approach
One important point to note is that, the order of tree traversal should match the order of string representation. Eg: if the tree traversal is post order then the string s should be
string s = leftString + ',' + rightString + ',' + to_string(root->val)
Messing up with the order may lead to the wrong answer.
BTW, very good explanation!!
Your explanation is the best.
Best explanation bhaiya, the only key point in solving the tree problems is to have trust in recursion
Bhai literally bhot pyara smjhaya aapne
Thanks good explanation
Legend is back!
Top notch explanation
Nice video of today
sbse best
Thanks a lot Nitin ❤️
Great Explanation as always
tooo good asusual 🙂
Mzaa aagya .. 🤩
The legend is back in the game.
best explaination
Thanks a lot ❤️❤️
Great Explanation
Thank you so much. 🙏😇
Bhaya you are back ❤️
really missed your explanations, when I got stuck in any of the daily questions.
As always 👏
You are awesome man. Loved it
Perfect
Finally after a long time
how did it handle duplicate entry in result vector
could you explain the time complexity for this
what is the TC?
0(n) or o 0(n^2) because of string concatenation
Another wonderful explanation , Like bhaiye ye approach kaise aayi string bnate hai , Like when i saw this question i used the map i was storing something like mapmpp;
Actually i also thought this, but we can’t know from a node that other subtree values will be same right.
Suppose a node value is 1 and it’s left child is 2 and right child is 3
You only store node 1 in map.
But there is another subtree with node 1 and it’s left child is 4 and right child is 5
Again you store 1 in map.
But these are not duplicate subtrees.
So I thought that storing as string can be the only solution.
@@codestorywithMIK bhaiya ye test cases sochne aajaye toh code approach ban ne lagegi ,mujhe ye test case ki problem hori
If you worried, that why should use comma so if you don't use them ,you will get wrong ans on 170th test case because it would consider 1,11,N and 11,1,N same😂
can't I store the dircetly the value od node in arraylist and then check whether this nod eexist in arraylist , in pre order tarversal
ans , output = [] , set()
def dfs(node) :
if not node :
return
if node in ans :
output.add(node)
else :
ans.append(node)
dfs(node.left)
dfs(node.right)
dfs(root)
print(output)
return list(output)
but this is not giving m eteh correct answer
if possible
pls show the leetcode part in dark mode pls
bhai recursive code samjha do
I have a question, can we have unique representation of tree with inorder traversal? I tried, it failed, but I am not able to get why
Yes, InOrder will fail. That's why he has used preorder (root -> left -> right)
yes but you have to use '' ,'
@@souravjoshi2293 but why does inorder fail
This was happen because inorder traversal Null come first so it your substring got also also same but that time your root is null so adding a Null root in our vector ans have no sence.
@@AnkitSingh-tm5dp Thanks man
i don't understand that by only storing (pushing) the root in the vector -- how are we getting the subtree?
Root is a pointer to subtree.
If you have the root pointer, they will traverse through it to verify the subtree
@@codestorywithMIK ok got it. thanks.
But bhaiya, if we do in-order traversal, tab to alag honge na output trees ke?
Yes, InOrder will fail. That's why he has used preorder (root -> left -> right)
@@souravjoshi2293 why its fail
Why not use else { mp[s]++ }
Why did it work without the else?
If we get a string say “1,2,3” multiple times, we want to add it only once in our result. We only add it to result once (i.e. when initially count was 1)
Now after getting the same string multiple times, we must update it’s count so that we don’t add it to result multiple times.
I tried this too. Then I did a dry run and found out that we will add duplicate results if we add else.
@@codestorywithMIK ohk got it thank you very much!
once we add the root into the vector mp[s] becomes 2 if it again repeats so it wont be added nxt time if the subtree repeats again