Find Duplicate Subtrees - Leetcode 652 - Python

[@NeetCodeIO]

I'll be traveling next week, so unfortunately I won't be able to do the daily problems for about 7 days. Will continue them as soon as I get back tho! 🚀

[@vixguy]

Enjoy your travels!!

[@shashankreddy4620]

this question can be done in O(n) time complexity we are storing strings so it will take O(n2) time

[@tunguyenxuan8296]

One leetcode a day, keeps unemployment away. Thanks for the content.

[@ancai5498]

Thanks, Neet for the clear solution, two major points here: 1. Time complexity, O(n^2), we need to visit each node, and the maximum length for hashing the string would be O(n) so overall is n * O(n); 2. The way this question asks has some issues, basically, we should only return sets of duplicate trees which does the map[key].size() == 1 come from. For eg, using the example in the video, node 4 itself is duplicated and should return {{2, 4}, {4}, {4}} if we don't add that check.

[@uptwist2260]

your explanations keep getting better. thanks for the daily

[@ferb7o2]

dude is in another level

[@puneetkumarsingh1484]

Thanks for the mind blowing solution. For me the key observation was the fact that adding the null value while serializing the Tree makes the resultant string unique to the tree itself which generally is not the case with only preorder, postorder or inorder traversal.

[@suchandranath1273]

@neetcode Great explaination, I followed the same logic , but instead of adding the node to the defualt dict i just maintained the count, it ran a bit faster and saves huge memory. I directly saved the node to the res. attaching my code: class Solution: def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: subtrees=defaultdict(int) def serialize(root): if root==None: return 'N' else: res=str(root.val)+","+serialize(root.left)+","+serialize(root.right) subtrees[res]+=1 if subtrees[res]==2: ans.append(root) return res res='' ans=[] serialize(root) return ans

[@infernoo365]

why did you use if subtrees[res]==2 ? defaultdict(int) returns 0 as default value

[@infernoo365]

i think it's because you have added subtrees[res]+=1 before if condition, if you write after if the condition becomes ==1

[@suchandranath1273]

@@infernoo365 Yes, I felt it clear if I write it this way. that was a bit confusing.

[@gaurangjotwani11]

You have the best explanations on entire KZbin! Will miss you for next week :(

[@sanjeevrajora7335]

concept of serialising the tree into string and storing it to hash map is a real hack, keep up the good job

[@yang5843]

Thanks Neetcode, you earned me the February Badge for this month's Leetcode.

[@aybarskeremtaskan]

Hi, I think "subtrees" could just be a `set` of strings (we do not need a key-value pair in this question).

[@tanish5662]

So as we are doing serialization and storing it a hashmap, we are having O(n) time complexity for lookup. Correct me if I am wrong.

[@ThuyNhuTieu]

Thank you so much sir, this is a brilliant video! But I have a question: is it a postorder-traversal rather than a preorder-traversal one? Since they will dive deep to (1) left -> (2) right -> (3) middle because of recursion? Thank you!

[@shubhampathak7926]

A small suggestion: you can put the difficulty of the problems on thumbnail! Thanks for the content btw.

[@xofjo6239]

This question is poorly described in leetcode. However, Neetcode explained it very well. Thank you!

[@vixguy]

Very nice! I came up with the same idea but had some trouble implementing it

[@anishkarthik4309]

your videos literally have the best explanations. love your videos and keep on doing it. Have a great trip.

[@akshatsinghbodh3067]

Thank you for starting this series!

[@madhavdua8588]

Thank you so much sir. Keep helping us by posting such content.

[@krateskim4169]

Awesome solution

[@alonebeast5310]

The Inorder traversal wont work for this example: [0,0,0,0,null,null,0,null,null,null,0] 0 node1-> 0 0 0 0

[@jazzyx95]

Good comment bro, I got stuck on the same test case with in-order. Your comment helped me figure out the issue!

[@Pinzauti]

Same problem, I don't understand why though

[@shawnzhang3736]

inorder failed at [0,0,0,0,null,null,0,null,null,null,0]. Only pre and post work.

[@sathwikmadhula9527]

I have a doubt? Why are we using strings. Would lists not work?

[@oliverheber599]

Why do we need to return s from the dfs function? It's not working when I don't return it, but I can't see why it's important?

[@vaishnavip4808]

I just had one small doubt.How are we really sure that the serialisation gives a unique subtree configuration.If the tree is not a BST, we need atleast one of preorder and postorder and an inorder to uniquely construct a tree.So just curious does this always work.And for inorder case, it might give 2 symmetric trees as equal even if they are not right?

[@SarveshRansubhe]

Thats y he said we should add null values.

[@jazzyx95]

@@SarveshRansubhe Adding 'null' still fails with InOrder, post and preorder works. To see why InOrder fails, see Alone Beast's comments.

[@aerialbaz3802]

I have replaced string representation with hashes and I think I have reduced TC and SC to linear. Tell me what I am doing wrong? Approach is to Use sha1 hash string representation to keep track of subtree. Since string representation can grow the size of tree, while sha1 hash string will be fixed length always. from hashlib import sha1 class Solution: def dfs(self, root) -> str: if not root: return "Null" else: left_hash = self.dfs(root.left) right_hash = self.dfs(root.right) res = left_hash + right_hash res += str(root.val) if res in self.hashes and res not in self.result_hashes: self.result_hashes.add(res) self.results.append(root) else: self.hashes.add(res) return sha1(res.encode('utf-8')).hexdigest() def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: self.hashes = set() self.result_hashes = set() self.results = [] self.dfs(root) return self.results

[@AllMightGaming-AMG]

Using a tuple instead of a string is more efficient

[@janaSdj]

Awesome ❤

[@sathwikmadhula9527]

Why hashing takes O(n) time complexity?

[@Walid-Sahab]

can anyone please explain me what line # 17 is doing ?

[@PulkitMalhotra]

Nice problem

[@irfanalahi380]

Though it is explained here, I am still not sure why the runtime is O(n^2). The DFS is touching all nodes only once and the string is being generated one step at a time. Wha am I missing?

[@m.kamalali]

Dic needs to compute the hash for key which is not simple here We need to get all nodes connected of this sub tree thats why we need n for hash So all time n for hash times n for dfs

[@mohamedsalama2743]

i thinks this postorder traversal not preorder

[@jaadui_chirag]

Did not work for [2,1,11,11,null,1]

[@infernoo365]

works for me

[@ahmadbodayr7203]

Bad test cases one of the two others namely inorder or postorder also works and the other doesnt which is wrong both of inorder and postorder shouldnt work as only preorder can give a unique tree string representation google the proof.

[@ShivangiSingh-wc3gk]

This solution fails for in-order