Bobek's blog

By Bobek, history, 8 years ago, In English

Could somebody give me a hint to the following question ?

Given balanced BST find the biggest subtree that is duplicated in that tree.

I've just came up with this problem and I don't know anything better than checking all pairs of nodes and setting them as roots. Then having those roots I can check what's the biggest duplicated subtree. Complexity will be O(n^3) . Is it possible to solve it more efficient ?

  • Vote: I like it
  • 0
  • Vote: I do not like it