BST — duplicate subtree

Правка en1, от 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 ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Bobek 2016-01-22 01:06:31 439 Initial revision (published)