Minimal Removal to Reach Target for Expression Tree

[hamidgasmi]

Given an (valid) expression tree (which is a binary tree that each node will either have 2 or 0 children. All leaf nodes will contain an integer number and all other nodes will contain "+" or "-"), you are asked to remove as minimal number of leaf nodes as possible so that 1). the resulting tree is still a valid expression tree; 2). the expression tree is evaluted to the given target value. If this is not possible, return -1.

Example:
Input: target = 3, Tree:

              -
            /    \
          +       -
        /  \     / \
      5     -   3   -1
	       /  \
	     3    2

Output: 1
Explanation: The given tree is evaluated as 5 + (3 - 2) - (3 - (-1)) = 2. If we remove the leaf node of 3, the tree becomes:

              -
            /    \
          +       -
        /  \      /  \
       5   2     3   -1

which is now evaluated as 5 + 2 - (3 - (-1)) = 3