Question $1$: Given a binary tree and an integer targetSum, return true if the tree has a

root$-$to$-$leaf path such that adding up all the values along the path equals targetSum.

Note: A leaf is a node with no children.

Return false if there does not exist a root$-$to$-$left path that adds up to the targetSum.

Find the appropriate search strategy that was discussed in the class $($heuristic$,$ DFS$,$ BFS

etc$)$ to traverse the input tree for the above problem statement.

Identify all the edge cases. $($such as if the tree node is NULL or reached to the end of the

tree.$)$

Explain the intuition behind why your search strategy is better than the other strategies

that we discussed in class.

Highlight the root$-$to$-$leaf path that you achieved from your strategy.

Evaluate your strategy$/$solution based upon the dimensions discussed in the class.

a$.$ Completeness

b$.$ Time and space complexity

c$.$ Optimality

Submit a PDF copy of your solution.

$1-$ An example that outputs TRUE for the problem statement:

Given the following tree and targetSum$=25,$ your search algorithm should return TRUE.

Explanation:

The path $1->7->6->11$ gives us the target sum $25.$ Hence, the algorithm returns true.

$2-$ An example that outputs FALSE for the problem statement:

Given the following tree and targetSum$=14,$ your search algorithm should return FALSE.

Explanation: The path $1->7$ sums up to $8.$ The path $1->9$ sums up to $10.$ The path $7->1->9$ or

$9->1->7$ sums up to $17.$ Hence, in no way we can get target sum $14.$ So the algorithm returns

false.