LeetCode 666: Path Sum IV

Problem Restatement

We are given an array nums.

Each integer in nums has exactly three digits and represents one node in a binary tree.

For a number DPV:

Depth and position are 1-based.

The tree depth is less than 5, so valid depths are from 1 to 4.

We need to return the sum of all root-to-leaf path sums.

Input and Output

Example function shape:

def pathSum(nums: list[int]) -> int:
    ...

Examples

Consider:

nums = [113, 215, 221]

Decode each number:

The tree is:

    3
   / \
  5   1

The root-to-leaf path sums are:

3 + 5 = 8
3 + 1 = 4

So the answer is:

8 + 4 = 12

Another example:

nums = [113, 221]

The tree is:

  3
   \
    1

There is one root-to-leaf path:

3 + 1 = 4

So the answer is:

4

First Thought: Build Tree Nodes

One direct solution is to create normal TreeNode objects.

For each encoded number, we decode its depth, position, and value. Then we connect each node to its parent.

This works, but it is more work than necessary.

The input already gives us enough information to traverse the tree directly.

We only need a way to quickly ask:

Does this node exist?

and:

What is its value?

A hash map is enough.

Key Insight

A node can be identified by its depth and position.

For a node at:

depth = d
position = p

its children are:

So we store:

(depth, position) -> value

Then we run DFS from the root:

(1, 1)

During DFS, we keep the current path sum.

When we reach a leaf, we add that path sum to the answer.

Leaf Detection

A node is a leaf if it has no left child and no right child.

For node (d, p), the possible children are:

(d + 1, 2 * p - 1)
(d + 1, 2 * p)

If neither key exists in the map, the node is a leaf.

Algorithm

1. Create an empty hash map called tree.
2. For every encoded number:
   • Extract depth.
   • Extract position.
   • Extract value.
   • Store the value using (depth, position) as the key.
3. Run DFS from (1, 1) with path sum 0.
4. At each node:
   • Add the node value to the path sum.
   • Check whether it has children.
   • If it has no children, add the path sum to the answer.
   • Otherwise, recursively visit existing children.
5. Return the answer.

Correctness

Each encoded integer uniquely identifies one node by its depth and position. The hash map stores exactly these nodes and their values.

For any node (d, p), the full-tree position rule gives its left child as (d + 1, 2p - 1) and its right child as (d + 1, 2p). Therefore, checking these two keys correctly determines which children exist.

The DFS starts at the root (1, 1) and follows only existing child positions. Since the input represents a valid connected binary tree, this visits every node reachable from the root.

The path sum passed through DFS is the sum of node values from the root to the current node. When a leaf is reached, this path is a complete root-to-leaf path, so adding the path sum to the answer is correct.

Every root-to-leaf path ends at exactly one leaf, and the DFS visits every leaf once. Therefore, the algorithm adds every root-to-leaf path sum exactly once and returns the required total.

Complexity

The recursion depth is at most 4, because the problem limits tree depth to less than 5.

Implementation

from typing import List

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        tree = {}

        for num in nums:
            depth = num // 100
            position = (num // 10) % 10
            value = num % 10

            tree[(depth, position)] = value

        answer = 0

        def dfs(depth: int, position: int, path_sum: int) -> None:
            nonlocal answer

            if (depth, position) not in tree:
                return

            path_sum += tree[(depth, position)]

            left = (depth + 1, 2 * position - 1)
            right = (depth + 1, 2 * position)

            if left not in tree and right not in tree:
                answer += path_sum
                return

            dfs(left[0], left[1], path_sum)
            dfs(right[0], right[1], path_sum)

        dfs(1, 1, 0)

        return answer

Code Explanation

We decode every three-digit number:

depth = num // 100
position = (num // 10) % 10
value = num % 10

For example, 215 becomes:

We store the node in a map:

tree[(depth, position)] = value

The DFS receives the current logical node location:

def dfs(depth: int, position: int, path_sum: int) -> None:

If the node does not exist, we stop:

if (depth, position) not in tree:
    return

Otherwise, we add the current node value:

path_sum += tree[(depth, position)]

Then we compute both child positions:

left = (depth + 1, 2 * position - 1)
right = (depth + 1, 2 * position)

If neither child exists, the current node is a leaf:

if left not in tree and right not in tree:
    answer += path_sum
    return

Otherwise, we continue to both children:

dfs(left[0], left[1], path_sum)
dfs(right[0], right[1], path_sum)

The missing child check inside DFS safely ignores nonexistent children.

Testing

def run_tests():
    s = Solution()

    assert s.pathSum([113, 215, 221]) == 12
    assert s.pathSum([113, 221]) == 4

    # Tree:
    #     1
    #    / \
    #   2   3
    #  /
    # 4
    assert s.pathSum([111, 212, 223, 314]) == 8

    # Single root.
    assert s.pathSum([117]) == 7

    # Tree:
    #       5
    #      /
    #     0
    #      \
    #       9
    assert s.pathSum([115, 210, 329]) == 14

    print("all tests passed")

run_tests()

Test meaning: