Equal Tree Partition

Given a binary tree with N nodes. Check whether it is possible to partition the tree to two trees
which have equal
sum of values after removing exactly one edge on the original tree.

Return 1 if the tree can be partitioned into two trees of equal sum else return 0.

Constraints

 2 <= N <= 100000
-10^9 <= Node values <= 10^9

For Example

Input 1:
                5
               /  \
              3    7
             / \  / \
            4  6  5  6
Output 1:
    1
    Explanation 1:
        Remove edge between 5(root node) and 7: 
        Tree 1 =                                               Tree 2 =
                        5                                                     7
                       /                                                     / \
                      3                                                     5   6    
                     / \
                    4   6
        Sum of Tree 1 = Sum of Tree 2 = 18

Input 2:
                1
               / \
              2   10
                  / \
                 20  2
Output 2:
     0
     Explanation 2:
        The given Tree cannot be partitioned.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Equal Tree Partition on Interview Code Editor
Sign Up
to access hints and editorial solutions for Equal Tree Partition

Discussion


Loading...
Click here to start solving coding interview questions