We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here is an explained solution:
1. Cut the tree from each node to create a new subtree
2. Hash the new subtree in a unique way from the center (whether one node center or two)
3. Compare all the subtrees using hashes such as sets.
4. The unique hashes will indicate the unique subtrees.
You can view an explanation here: Problem_Solving/Tree Isomorphism.ipynb in my github. MohamedYahiaSan
You will have to tune it for the proplem a little bit. However, it still doesn't answer the complexity for the last 4 tests.
Another approach which is the best. However, it also didn't return perfct answers with me is to stack all leaves of the subtrees. Then starting form the leaves hash the tree in a unique way. However, it still doesn't overcome the time complexity for the last few tasks somehow!!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Jenny's Subtrees
You are viewing a single comment's thread. Return to all comments →
Here is an explained solution: 1. Cut the tree from each node to create a new subtree 2. Hash the new subtree in a unique way from the center (whether one node center or two) 3. Compare all the subtrees using hashes such as sets. 4. The unique hashes will indicate the unique subtrees. You can view an explanation here: Problem_Solving/Tree Isomorphism.ipynb in my github. MohamedYahiaSan
You will have to tune it for the proplem a little bit. However, it still doesn't answer the complexity for the last 4 tests. Another approach which is the best. However, it also didn't return perfct answers with me is to stack all leaves of the subtrees. Then starting form the leaves hash the tree in a unique way. However, it still doesn't overcome the time complexity for the last few tasks somehow!!