Path Sum

Q: What is the time complexity of Path Sum?

O(n) : each node is visited at most once, and the search can stop at the first leaf that matches. The extra space is O(h) for the path being explored, as call frames or as entries on your own stack.

EasyTree traversal

+10

You get a binary tree stored in the array tree in level order, and a number targetSum. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries. Return true if some path from the root down to a leaf has values that add up to targetSum, and false otherwise. A leaf is a node whose two child spots are both empty.

Function

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: the binary tree in level order, with -1 for an empty spot
targetSuminteger: the total a root-to-leaf path must reach
Returnsboolean: true if some root-to-leaf path adds up to targetSum, false otherwise

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 1000.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.
0 ≤ targetSum ≤ 15000

Examples

Input: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Output: true
Explanation: The path 3, 9, 2 (indexes 0, 1, 4) adds up to 14, and the 2 at index 4 is a leaf.

Input: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Output: false
Explanation: 3 + 9 = 12, but the 9 has a child, so no path ends there. The three root-to-leaf paths add up to 14, 10 and 16, and none of them is 12.

Input: tree = [4, -1, -1]targetSum = 4
Output: true
Explanation: Both child spots of the root are empty, so the root is a leaf on its own. The path that holds only 4 adds up to 4.

Follow-up

Can you count the paths that add up to targetSum if a path may start at any node and end at any node below it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Only whole paths count, from the root down to a leaf. A running total can hit targetSum at a node that still has children, which does not count. So carry the path's sum down to every node, as a parameter or on a stack, and compare it with the target only at leaves.

Recursion on the remaining sum

Intuition

A path that adds up to targetSum starts with the root's value, so the rest of it, which starts at one of the root's children, must add up to targetSum minus that value. That is the same question on a smaller tree. Subtract each node's value on the way down; at a leaf the path ends, so the answer is whether nothing is left.

In the first example the root leaves 14 - 3 = 11, the 9 leaves 2 and the leaf 2 leaves 0. In the second, the 9 already leaves 0, but it has a child, so the search goes on. Each node is visited once, O(n) time, and the call stack holds one frame per level, at most 15.

Algorithm

Write walk(i, remaining) and subtract tree[i] from remaining.
If both child spots of i are empty (index past the end or -1), return whether remaining is 0.
Otherwise return true if walk on a real left child or on a real right child returns true.
Return walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Depth-first search with an explicit stack

Intuition

The recursion keeps one number per call. Keep it yourself instead, on a stack next to each node: the sum of the path from the root down to that node. Start with (0, tree[0]); each child gets its parent's sum plus its own value. Pop a pair. If the node is a leaf with sum targetSum, you are done; otherwise push its real children.

Each real node is pushed once, O(n) time, and the stack holds about one waiting sibling per level, O(h). The same loop works on a deep pointer-based tree, where recursion could run out of stack.

Algorithm

Push (0, tree[0]) on a stack.
Pop a pair (i, total) and look at the child spots 2*i+1 and 2*i+2.
If neither child is real and total equals targetSum, return true.
Push each real child c as (c, total + tree[c]).
When the stack is empty, return false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Pitfalls and edge cases

Comparing the sum at every node. In the second example 3 + 9 = 12 matches at the 9, which has a child, so the answer is false.
Letting an empty child spot end a path. Then the 9 in the second example ends a path through its empty left spot.
Forgetting the root alone. A single node is a leaf, so [4] with target 4 is true, and so is [0] with target 0.
Reading past the end of the array. A leaf near the end can have child indexes past the last entry.
Mixing up the offset in Lua and R. Keep node indexes 0-based for 2*i+1 and read tree[i + 1].

Frequently asked questions3

What is the time complexity of Path Sum?

O(n): each node is visited at most once, and the search can stop at the first leaf that matches. The extra space is O(h) for the path being explored, as call frames or as entries on your own stack.

Can Path Sum be solved with BFS?

Yes. Put pairs of a node and its path sum in a queue instead of a stack, and check each leaf as it comes out. The time is still O(n), but the queue can hold a whole level, about half the nodes of a full tree, while a stack holds about one node per level.

How do you find every path that adds up to the target?

Keep the list of nodes on the current path as you go down, copy it into the answer at each leaf whose sum matches, and remove the last node when you go back up. The traversal stays the same. Copying the paths can cost more than the traversal when many leaves match.

def hasPathSum(tree, targetSum):
    # Write code here

Test #1

Test #2

Test #3

Arguments

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Expected Output

true