BST — duplicate subtree

Revision en1, by Bobek, 2016-01-22 01:06:31

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Bobek 2016-01-22 01:06:31 439 Initial revision (published)