I know that a number of valid parantheses is nth catalan number. The same is for number of binary search trees. Is there any way to convert valid parantheses sequence to binary search tree with keys 1-n?

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3337 |

3 | Petr | 3298 |

4 | W4yneb0t | 3218 |

5 | Radewoosh | 3216 |

6 | OO0OOO00O0OOO0O0…O | 3188 |

7 | Syloviaely | 3168 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | fateice | 3099 |

# | User | Contrib. |
---|---|---|

1 | tourist | 184 |

2 | rng_58 | 170 |

3 | csacademy | 165 |

4 | Petr | 158 |

5 | Swistakk | 154 |

6 | lewin | 149 |

7 | Errichto | 147 |

8 | matthew99 | 146 |

9 | adamant | 141 |

9 | Zlobober | 141 |

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 ?

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2018 17:51:33 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|