Largest Proper Subtree — Solution & Editorial

Back to the Problem

Compute subtree sizes bottom-up (post-order over a BFS order works iteratively) and take the maximum over non-root nodes.

Complexity: O(N)