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. 1. 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. 2. Identify all the edge cases. (such as if the tree node is NULL or reached to the end of the tree.) 3. Explain the intuition behind why your search strategy is better than the other strategies that we discussed in class. 4. Highlight the root-to-leaf path that you achieved from your strategy. 5. Evaluate your strategy/solution based upon the dimensions discussed in the class. MIS 429 Artificial Intelligence Assignment 1 a. Completeness b. Time and space complexity c. Optimality 6. Submit a PDF copy of your solution. 2 1- An example that outputs TRUE for the problem statement: Given the following tree and targetSum=25, your search algorithm should return TRUE. H 5 6 5 Explanation: The path 17611 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 17 sums up to 8. The path 1-9 sums up to 10. The path 719 or 917 sums up to 17. Hence, in no way we can get target sum 14. So the algorithm returns false. # 1 9