Find Duplicate Subtrees (Leetcode - 652) - (GOOGLE) : Explanation ➕ Live Coding

[@r.beditz3674]

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; } }

[@satyasanjay1339]

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; } }

[@krishnaradhey2814]

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 :-).....

[@iamnoob7593]

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.

[@041nitinkumar7]

sbse best

[@codestorywithMIK]

Thanks a lot Nitin ❤️

[@KrishKanani-ql1nq]

Perfectly Explained, with nice and easy approach

[@ravikumar-nl7zt]

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!!

[@rahulmaurya6451]

Bhai literally bhot pyara smjhaya aapne

[@krishnaneeldey8722]

Your explanation is the best.

[@pritishpattnaik4674]

Best explanation bhaiya, the only key point in solving the tree problems is to have trust in recursion

[@iamnoob7593]

Thanks good explanation

[@thekindspill]

Top notch explanation

[@jogindrasingh6139]

Nice video of today

[@altafmazhar7762]

The legend is back in the game.

[@anshumanpatidar8599]

Mzaa aagya .. 🤩

[@thedarkknight1865]

best explaination

[@codestorywithMIK]

Thanks a lot ❤️❤️

[@philosphize]

Great Explanation as always

[@vamsimadugula8524]

Great Explanation

[@codestorywithMIK]

Thank you so much. 🙏😇

[@STR09]

really missed your explanations, when I got stuck in any of the daily questions.

[@vishalplayzz2580]

tooo good asusual 🙂

[@thegreekgoat98]

Legend is back!

[@riyakushwaha4347]

could you explain the time complexity for this

[@soumyadipmajumdar4306]

what is the TC? 0(n) or o 0(n^2) because of string concatenation

[@adhikari669]

Bhaya you are back ❤️

[@susmitjaiswal136]

how did it handle duplicate entry in result vector

[@shabananoor9423]

Perfect

[@ayushjain386]

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;

[@codestorywithMIK]

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.

[@ayushjain386]

@@codestorywithMIK bhaiya ye test cases sochne aajaye toh code approach ban ne lagegi ,mujhe ye test case ki problem hori

[@souravjoshi2293]

You are awesome man. Loved it

[@VineetKumar-pj1bk]

As always 👏

[@neelakshisoni6118]

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

[@madhavgupta2002]

if possible pls show the leetcode part in dark mode pls

[@Ash-fo4qs]

i don't understand that by only storing (pushing) the root in the vector -- how are we getting the subtree?

[@codestorywithMIK]

Root is a pointer to subtree. If you have the root pointer, they will traverse through it to verify the subtree

[@Ash-fo4qs]

@@codestorywithMIK ok got it. thanks.

[@sakshamsharma648]

Finally after a long time

[@akhilesh_ku]

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😂

[@girikgarg8]

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

[@souravjoshi2293]

Yes, InOrder will fail. That's why he has used preorder (root -> left -> right)

[@VineetKumar-pj1bk]

yes but you have to use '' ,'

[@girikgarg8]

@@souravjoshi2293 but why does inorder fail

[@AnkitSingh-tm5dp]

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.

[@souravjoshi2293]

@@AnkitSingh-tm5dp Thanks man

[@AnkitPandey-s9h]

bhai recursive code samjha do

[@drbullah1388]

But bhaiya, if we do in-order traversal, tab to alag honge na output trees ke?

[@souravjoshi2293]

Yes, InOrder will fail. That's why he has used preorder (root -> left -> right)

[@Danish-saifi1]

@@souravjoshi2293 why its fail

[@recessionriche]

Why not use else { mp[s]++ } Why did it work without the else?

[@codestorywithMIK]

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.

[@souravjoshi2293]

I tried this too. Then I did a dry run and found out that we will add duplicate results if we add else.

[@recessionriche]

@@codestorywithMIK ohk got it thank you very much!

[@vishalplayzz2580]

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