algoadvance

  1. What is the structure of the input? - The input consists of a binary tree and an integer target sum.
  2. Can the tree contain negative values? - Yes, the tree can contain negative values.
  3. What should be returned? - We need to return True if there exists a root-to-leaf path such that the sum of the node values equals the target sum, otherwise False.
  4. Definition of a leaf node? - A leaf node is a node with no children.

Strategy:

  1. Depth-First Search (DFS):
    • We can use a depth-first search approach to explore all paths from the root to the leaf nodes.
    • At each node, subtract the node’s value from the target sum and check if we have reached a leaf node.
    • If we reach a leaf node and the remaining target sum is zero, then we have found a valid path.
  2. Recursive Function:
    • Create a helper recursive function that traverses the tree and checks the sums.
  3. Base Case:
    • If the current node is None, return False (we’ve reached beyond a leaf without success).
    • If it’s a leaf node and the current sum is zero after subtracting the node’s value, return True.
## Code Implementation

# 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

def hasPathSum(root: TreeNode, target_sum: int) -> bool:
    # Helper function to perform the DFS
    def dfs(node: TreeNode, current_sum: int) -> bool:
        if not node:
            return False
        
        current_sum -= node.val
        
        if not node.left and not node.right:  # if it's a leaf node
            return current_sum == 0
        
        return dfs(node.left, current_sum) or dfs(node.right, current_sum)

    return dfs(root, target_sum)

Time Complexity:

Would you like to proceed with this implementation or have any other questions?

Try our interview co-pilot at AlgoAdvance.com