Approach #1: DepthFirst Search [Accepted]
Intuition and Algorithm
After removing some edge from parent
to child
, (where the child
cannot be the original root
) the subtree rooted at child
must be half the sum of the entire tree.
Let's record the sum of every subtree. We can do this recursively using depthfirst search. After, we should check that half the sum of the entire tree occurs somewhere in our recording (and not from the total of the entire tree.)
Our careful treatment and analysis above prevented errors in the case of these trees:
0 / \ 1 1 0 \ 0
Complexity Analysis

Time Complexity: where is the number of nodes in the input tree. We traverse every node.

Space Complexity: , the size of
seen
and the implicit call stack in our DFS.
Analysis written by: @awice.