Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
EDGE CASE
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
If you are dealing with Binary Trees some common techniques you can employ to help you solve the problem:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Lets build the sum as we progress through the nodes. We will remove values from our targetSum as we progress. Upon reaching a leaf node, check if value is equal to targetSum.
1. Set basecase to root is None, return false
2. Upon reaching a leaf node, check if value is equal to targetSum
3. Recursively proceed to next node and remove value from targetSum
⚠️ Common Mistakes
Implement the code to solve the algorithm.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
# Set basecase to root is None, return false
if not root:
return False
# Upon reaching a leaf node, check if value is equal to targetSum
if not root.left and not root.right:
return targetSum == root.val
# Recursively proceed to next node and remove value from targetSum
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
// Set basecase to root is None, return false
if (root == null) return false;
// Upon reaching a leaf node, check if value is equal to targetSum
if (root.left == null && root.right == null && root.val == sum) return true;
// Recursively proceed to next node and remove value from targetSum
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number nodes in tree
O(N)
because we need to visit each node in binary tree.O(1)
if we do not count the recursion stack. The recursion stack will cost us O(N)
if we have a linked list like tree. O(logN)
in the average case.