Given a binary tree with
n nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.
Input: 5 / \ 10 10 / \ 2 3 Output: True Explanation: 5 / 10 Sum: 15 10 / \ 2 3 Sum: 15
Input: 1 / \ 2 10 / \ 2 20 Output: False Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.
Intuition and Algorithm\n
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.)\n
Our careful treatment and analysis above prevented errors in the case of these trees:\n
0\n / \\\n-1 1\n\n 0\n \\\n 0\n
Time Complexity: where is the number of nodes in the input tree. We traverse every node.\n
Space Complexity: , the size of
seen and the implicit call stack in our DFS.
Analysis written by: @awice.\n