[MEDIUM] #1080 - Insufficient Nodes in Root to Leaf Paths

[hackdartstorm]

🎯 Problem: Insufficient Nodes in Root to Leaf Paths

📖 The Real Problem

You are given a binary tree and a target sum. Your task is to determine if the tree has any root-to-leaf path where the sum of all node values along the path equals the target sum.

Why this problem exists:

• Many tree algorithms require understanding path traversal
• This is a fundamental problem that tests understanding of recursion and tree traversal
• It's a building block for more complex tree path problems

💡 Why This Matters

Real-world applications:

• Decision trees in machine learning use similar path evaluation
• Network routing algorithms evaluate paths with cost constraints
• Game trees in AI evaluate move sequences with score targets
• File system navigation with size/depth constraints

Skills you'll develop:

• ✅ Recursive tree traversal
• ✅ Path sum calculation
• ✅ Base case identification in trees
• ✅ Backtracking concepts

📋 Contributor Tasks

Step 1: Understand the Problem

1. Read the problem statement carefully
2. Draw a simple binary tree on paper
3. Trace a few root-to-leaf paths manually
4. Calculate path sums for each path

Step 2: Plan Your Approach

1. Decide on traversal method (DFS recommended)
2. Identify base cases:
   • Empty node (null)
   • Leaf node (no children)
3. Plan recursive strategy:
   • Subtract current node value from target sum
   • Recurse on left and right subtrees

Step 3: Implement the Solution

1. Create a function that takes (node, target_sum)
2. Handle the null node case
3. Handle the leaf node case
4. Recurse on children with updated target sum
5. Return True if either subtree has a valid path

Step 4: Test Your Solution

1. Test with empty tree
2. Test with single node tree
3. Test with tree where path exists
4. Test with tree where no path exists
5. Test with negative values

✅ Expected Outcome

Your solution should:

Function Signature:

def hasPathSum(root, targetSum):
    """
    Determine if tree has root-to-leaf path with target sum.
    
    Args:
        root: TreeNode - root of binary tree
        targetSum: int - target sum to find
    
    Returns:
        bool: True if path exists, False otherwise
    """

Expected Behavior:

• ✅ Returns True if ANY root-to-leaf path sums to target
• ✅ Returns False if NO path matches target
• ✅ Handles empty tree (returns False)
• ✅ Handles single node tree correctly
• ✅ Works with negative values in nodes

Example Test Cases:

# Test 1: Path exists
# Tree:     5
#          / \
#         4   8
#        /   / \
#       11  13  4
#      /  \      \
#     7    2      1
hasPathSum(root, 22)  # Returns: True (5→4→11→2 = 22)

# Test 2: No path exists
# Tree:     1
#          / \
#         2   3
hasPathSum(root, 5)  # Returns: False

# Test 3: Empty tree
hasPathSum(None, 0)  # Returns: False

# Test 4: Single node
# Tree:     5
hasPathSum(root, 5)  # Returns: True
hasPathSum(root, 3)  # Returns: False

📚 Additional Context & References

Tree Node Structure

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Key Concepts to Understand

1. Root-to-Leaf Path:

• Must start at root
• Must end at a leaf node (node with no children)
• Cannot stop at intermediate nodes

2. DFS Traversal:

# Typical DFS pattern for trees
def dfs(node):
    if not node:
        return
    # Process current node
    dfs(node.left)
    dfs(node.right)

3. Base Cases:

• Null node: Return False (no path)
• Leaf node: Check if remaining sum equals node value

Hints (Use Only If Stuck!)

💡 Hint 1

Think about what happens when you reach a leaf node. What should you check?

💡 Hint 2

At each node, you can subtract its value from the target sum and pass the remaining sum to children.

💡 Hint 3

A leaf node is a node where both left and right children are None.

Complexity Analysis

Time Complexity: O(n)

• Visit each node once in worst case
• n = number of nodes in tree

Space Complexity: O(h)

• Recursion stack depth
• h = height of tree
• Worst case: O(n) for skewed tree
• Best case: O(log n) for balanced tree

Related Problems

Once you solve this, try these related problems:

• Path Sum II - Find ALL paths that sum to target
• Binary Tree Maximum Path Sum - Find maximum path sum (any path)
• Sum Root to Leaf Numbers - Treat paths as numbers

Helpful Resources

• Binary Tree Traversal
• DFS on Trees
• LeetCode 112 - Path Sum

📝 Notes

• A leaf node is defined as a node with NO children
• Empty tree (root = None) should return False
• Node values can be negative
• Target sum can be negative
• Path must go from root ALL THE WAY to a leaf

---

Ready to contribute?

1. Fork the repository
2. Create your solution file
3. Test thoroughly
4. Submit a pull request!

File Location: exercises/1000_programs/medium/1080_insufficient_nodes_path_sum.py

🚀 Happy coding!

[Osamsami]

Hi @hackdartstorm, I'm a beginner and I'd like to solve this issue. I have a good understanding of binary trees and DFS. Could you please assign this to me?