Approach #1: Depth-First Search [Accepted]
Intuition and Algorithm
After removing some edge from
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 depth-first 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
Time Complexity: where is the number of nodes in the input tree. We traverse every node.
Space Complexity: , the size of
seenand the implicit call stack in our DFS.
Analysis written by: @awice.