Path Sum

Q: What is the time complexity of Path Sum?

Each node is visited at most once, so the time is O(n) , and the search can stop at the first leaf that matches. The extra space is O(h) for the path being explored, either 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 with no children: both of its child spots are 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.

+14 hidden tests on Submit

Follow-up

Can you count the paths that add up to targetSum when a path may start at any node and end at any node below it, not only run from the root to a leaf?

Hints

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

0 of 3 opened

Solution

The question is about whole paths, from the root all the way to a leaf. A running total can reach targetSum part way down, at a node that still has children, and that does not count. So you carry the sum of the path so far to every node and compare it with the target only at the leaves. Recursion carries that sum as a parameter; a stack carries it next to each node.

Recursion on the remaining sum

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [3, 9, 6, -1, 2, 1, 7], the root 3 has children at indexes 1 and 2, and the 9 at index 1 has an empty left spot at 3 and the 2 at index 4 on its right.

Now the idea. A path that adds up to targetSum starts with the root's value, so the rest of the path, 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 there is whether nothing is left over.

In the first example the root leaves 14 - 3 = 11, the 9 leaves 2, and the leaf 2 leaves 0: true. In the second example the 9 already leaves 0, but it has a child, so the search goes on, and its leaf ends at -2. Every node is visited at most once, O(n) time, and the call stack holds one frame per level, O(h), at most 15 frames here (a depth of 14 counts the edges below the root).

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: how much of the target is still missing. You can keep a number like that yourself, on a stack next to each node, and drop the calls. Store the sum of the path from the root down to the node, the node included. Start with (0, tree[0]), and give each child its parent's sum plus its own value.

Pop a pair. If the node is a leaf and its sum equals targetSum, you are done. Otherwise push its real children. In the first example the right side comes off the stack first: the leaves 7 and 1 carry 16 and 10. Then (1, 12) for the 9 is popped. It is not a leaf, so it pushes (4, 14), a leaf with the right sum.

Each real node is pushed once, so the time is O(n), and the search stops at the first leaf that matches. The stack holds the waiting siblings along the current path, about one per level, O(h) space. 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

Almost every bug in this problem is about where a path ends.

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. Compare only at leaves.
Treating an empty child spot as the end of a path. If walk on an empty spot returns remaining == 0, the 9 in the second example counts as a leaf through its empty left spot. A node is a leaf only when both spots are empty.
Forgetting the root alone. A single node is a leaf, so [4] with targetSum = 4 is true, and so is [0] with targetSum = 0.
Cutting the search off once the total passes the target. Values here are never negative, so that is safe in this problem, but the same code gives wrong answers as soon as a tree can hold negative values.
Reading past the end. A leaf near the end of the array can have child indexes past its last entry, because the array may stop right after the last node. Check the index before reading tree[c].
Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

What is the time complexity of Path Sum?

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

Why does Path Sum only check the sum at leaf nodes?

The problem asks for a root-to-leaf path, and a path that stops at a node with children is not one. Checking at every node returns true too often, for example when the root's value alone equals the target but the root has a child. A node ends a path only when both of its child spots are empty.

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; only the bookkeeping grows. Copying the paths can cost more than the traversal itself when many leaves match.

Python

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

Test cases

Case 1

Case 2

Case 3

Input

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

Expected

true