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! 🚀
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.
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.
@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
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!
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
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?
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?
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
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.
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! 🚀
Enjoy your travels!!
this question can be done in O(n) time complexity
we are storing strings so it will take O(n2) time
One leetcode a day, keeps unemployment away. Thanks for the content.
your explanations keep getting better. thanks for the daily
dude is in another level
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.
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.
You have the best explanations on entire TH-cam! Will miss you for next week :(
@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
why did you use if subtrees[res]==2 ? defaultdict(int) returns 0 as default value
i think it's because you have added subtrees[res]+=1 before if condition, if you write after if the condition becomes ==1
@@infernoo365 Yes, I felt it clear if I write it this way. that was a bit confusing.
Thanks Neetcode, you earned me the February Badge for this month's Leetcode.
concept of serialising the tree into string and storing it to hash map is a real hack, keep up the good job
your videos literally have the best explanations. love your videos and keep on doing it. Have a great trip.
Very nice! I came up with the same idea but had some trouble implementing it
Hi, I think "subtrees" could just be a `set` of strings (we do not need a key-value pair in this question).
Thank you for starting this series!
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.
A small suggestion: you can put the difficulty of the problems on thumbnail!
Thanks for the content btw.
Thank you so much sir. Keep helping us by posting such content.
This question is poorly described in leetcode. However, Neetcode explained it very well. Thank you!
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
Good comment bro, I got stuck on the same test case with in-order. Your comment helped me figure out the issue!
Same problem, I don't understand why though
Awesome solution
inorder failed at [0,0,0,0,null,null,0,null,null,null,0]. Only pre and post work.
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!
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?
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
Using a tuple instead of a string is more efficient
I have a doubt? Why are we using strings. Would lists not work?
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?
Thats y he said we should add null values.
@@SarveshRansubhe Adding 'null' still fails with InOrder, post and preorder works. To see why InOrder fails, see Alone Beast's comments.
Awesome ❤
Nice problem
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?
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
can anyone please explain me what line # 17 is doing ?
Why hashing takes O(n) time complexity?
i thinks this postorder traversal not preorder
Did not work for [2,1,11,11,null,1]
works for me
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.
This solution fails for in-order