DSA Interview Prep · Lesson

Path Sum and Lowest Common Ancestor

Solve root-to-leaf path sum, all-paths-sum, and lowest-common-ancestor for a general binary tree using recursive descent.

Root-to-Leaf Path Sum

The path sum problem asks whether any root-to-leaf path sums to a target. Pass the remaining target down the recursion, subtracting each node's value. At a leaf, check if the remaining equals the leaf's value. This avoids maintaining an explicit path list and is both space-efficient and clean. Edge case: an empty tree has no paths, so return False immediately.

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

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:  # leaf
        return root.val == target
    remain = target - root.val
    return (has_path_sum(root.left, remain) or
            has_path_sum(root.right, remain))

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22))  # True: 5->4->11->2

All Root-to-Leaf Paths

To enumerate all paths, maintain a running path list. At each recursive call, append the current node's value, recurse into children, then pop on return (backtrack). At a leaf, record a snapshot (list(path)) of the current path. This pattern — choose, recurse, unchoose — is the foundation of backtracking on trees.

def all_path_sums(root, target):
    results = []

    def dfs(node, path, remaining):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            results.append(list(path))  # snapshot
        else:
            dfs(node.left, path, remaining - node.val)
            dfs(node.right, path, remaining - node.val)
        path.pop()  # backtrack

    dfs(root, [], target)
    return results

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22))  # [[5,4,11,2]]

All lessons in this course

← Back to DSA Interview Prep