Path Sum Root to Leaf in Binary Tree in DSA Go

Mental Model

We want to check if there is a path from the top of the tree to any bottom leaf where the numbers add up to a target sum.

Analogy: Imagine walking down a tree from the top to the bottom, adding numbers on each branch. We want to see if any path adds up exactly to a certain number, like counting steps to reach a treasure.

    5
   / \
  4   8
 /   / \
11  13  4
/  \      \
7    2      1

Dry Run Walkthrough

Input: Tree: 5->4->11->7 (leaf), target sum = 22

Goal: Find if any root-to-leaf path sums to 22

Step 1: Start at root node 5, current sum needed is 22

5 (need 22)

Why: We begin at the top and want to find a path that sums to 22

Step 2: Go left to node 4, subtract 5 from sum, now need 17

5 -> [4] (need 17)

Why: We move down left branch, updating the remaining sum needed

Step 3: Go left to node 11, subtract 4 from sum, now need 13

5 -> 4 -> [11] (need 13)

Why: Continue down left branch, updating sum needed

Step 4: Go left to node 7, subtract 11 from sum, now need 2

5 -> 4 -> 11 -> [7] (need 2)

Why: Move to leaf candidate, check if sum matches

Step 5: Node 7 is leaf but need 2, path sum not matched, backtrack

5 -> 4 -> 11 -> 7 (leaf, need 2)

Why: Leaf reached but sum does not match, so this path fails

Step 6: Go right to node 2 from 11, subtract 11 from sum, now need 2

5 -> 4 -> 11 -> [2] (need 2)

Why: Try other leaf on this branch

Step 7: Node 2 is leaf and need is 2, path sum matched

5 -> 4 -> 11 -> 2 (leaf, need 2)

Why: Found a path where sum matches target

Result:

5 -> 4 -> 11 -> 2 -> null (path sum 22 found)

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode defines a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// hasPathSum checks if there is a root-to-leaf path with given sum
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    // If leaf node, check if value equals targetSum
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }
    // Recursively check left and right subtrees with reduced sum
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

func main() {
    // Build tree from dry run example
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 11}
    root.Left.Left.Left = &TreeNode{Val: 7}
    root.Left.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 13}
    root.Right.Right = &TreeNode{Val: 4}
    root.Right.Right.Right = &TreeNode{Val: 1}

    targetSum := 22
    fmt.Println(hasPathSum(root, targetSum))
}

if root == nil { return false }

handle empty node - no path here

if root.Left == nil && root.Right == nil { return root.Val == targetSum }

check if leaf node matches remaining sum

return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)

recurse left and right with updated sum, return true if any path matches

Output

true

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative BFS, recursion is simpler but uses call stack; BFS uses queue and may use more memory for wide trees

Edge Cases

Empty tree

Returns false because no paths exist

DSA Go

if root == nil {
        return false
    }

Single node tree where node value equals target sum

Returns true because root is leaf and matches sum

DSA Go

if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }

Single node tree where node value does not equal target sum

Returns false because no matching path

DSA Go

if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }

When to Use This Pattern

When asked if a root-to-leaf path sums to a target, use recursion to subtract node values and check leaves for exact match.

Common Mistakes

Mistake: Checking sum only at nodes, not at leaves, causing false positives
Fix: Only confirm sum match when at leaf nodes (no children)

Mistake: Not subtracting current node value from target sum before recursion
Fix: Pass targetSum - root.Val to recursive calls

Summary

Checks if any root-to-leaf path in a binary tree sums to a target value.

Use when you need to verify if a path with a specific sum exists from top to bottom.

The key is to subtract node values as you go down and confirm sum only at leaf nodes.