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

Transcribed Image Text:

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 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

Answer rating: 100% (QA)

Solutions Step 1 1 The appropriate search strategy for this problem is a DepthFirst Search DFS algorithm DFS is a tree traversal algorithm that explores as far as possible along each branch before bac... View the full answer