LeetCode 666 - Path Sum IV

This problem encodes a binary tree into a compact array of three-digit integers. Each integer stores three pieces of information: - The hundreds digit represents the depth of the node. - The tens digit represents the node's position within that depth level.

leetcodemediumarrayhash-tabletreedepth-first-searchbinary-tree

LeetCode Problem 666

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem encodes a binary tree into a compact array of three-digit integers. Each integer stores three pieces of information:

  • The hundreds digit represents the depth of the node.
  • The tens digit represents the node's position within that depth level.
  • The units digit represents the node's actual value.

For example, the integer 215 means:

  • Depth = 2
  • Position = 1
  • Value = 5

The positions follow the indexing rules of a full binary tree. That means:

  • A node at position p has:

  • Left child at position 2 * p - 1

  • Right child at position 2 * p

The input array is already sorted and represents a valid connected tree whose depth is less than 5.

The goal is to compute the sum of every root-to-leaf path. A root-to-leaf path sum is the sum of all node values encountered while moving from the root down to a leaf node.

For example, if the tree has two root-to-leaf paths:

  • 3 -> 5
  • 3 -> 1

Then the total answer is:

(3 + 5) + (3 + 1) = 12

The constraints are very small:

  • At most 15 nodes
  • Maximum depth is 4

This means even relatively inefficient solutions would still run quickly. However, the problem is primarily testing whether we correctly interpret the tree encoding and traverse the structure properly.

Several edge cases are important:

  • A tree may contain only the root node.
  • A node may have only one child.
  • Leaves are not explicitly marked, we must detect them.
  • Since the tree is sparse, positions may skip values.
  • We cannot construct children using array indices alone because the encoding uses logical tree positions, not contiguous storage.

The problem guarantees the input represents a valid connected binary tree, so we do not need to validate malformed structures.

Approaches

Brute Force Approach

A straightforward solution is to first reconstruct the entire binary tree using actual tree node objects. We would parse every encoded number, create nodes, connect parents and children based on the depth-position relationship, and then run a standard DFS traversal to compute all root-to-leaf path sums.

This approach is correct because once the tree is reconstructed, the problem becomes a standard binary tree path sum traversal problem.

However, constructing explicit tree nodes is unnecessary overhead. The input already contains enough information to identify parent-child relationships directly through arithmetic on depth and position values.

Although the constraints are small enough that this solution would pass comfortably, it performs extra work and uses more memory than necessary.

Optimal Approach

The key observation is that we never actually need to build the binary tree structure.

Each node can be uniquely identified using:

(depth, position)

We can store all nodes in a hash map where:

key = depth * 10 + position
value = node value

Then, during DFS:

  • We compute the current path sum.
  • We derive the potential left and right child positions mathematically.
  • If neither child exists in the hash map, the current node is a leaf.
  • Otherwise, we recursively continue traversal.

This works because the encoding itself already contains the full structure of the tree.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Explicitly constructs the binary tree before DFS
Optimal O(n) O(n) Uses a hash map and traverses directly from encoded coordinates

Algorithm Walkthrough

  1. Create a hash map to store all nodes.

For every number in nums, extract:

  • Depth: num // 100
  • Position: (num // 10) % 10
  • Value: num % 10

Store the node value using:

key = depth * 10 + position

This allows constant-time lookup for any node. 2. Define a DFS function.

The DFS function should accept:

  • Current depth
  • Current position
  • Current accumulated path sum

At each step, we add the current node's value to the running sum. 3. Compute child positions.

For a node at position p:

  • Left child position = 2 * p - 1
  • Right child position = 2 * p

Both children are at depth d + 1. 4. Check whether children exist.

Build keys for the potential children:

left_key = (d + 1) * 10 + (2 * p - 1)
right_key = (d + 1) * 10 + (2 * p)

Use the hash map to determine whether each child exists. 5. Detect leaf nodes.

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

Add the current path sum to the final answer. 6. Recursively traverse existing children.

If a child exists, continue DFS with the updated path sum. 7. Start DFS from the root.

The root is always the first node in the sorted input.

Why it works

The algorithm works because every node's location uniquely determines where its children must be in a full binary tree indexing system. By storing nodes in a hash map keyed by (depth, position), we can directly navigate the implicit tree structure without constructing actual tree nodes. DFS guarantees that every root-to-leaf path is explored exactly once, and each leaf contributes precisely its path sum to the final answer.

Python Solution

from typing import List

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

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

            key = depth * 10 + position
            nodes[key] = value

        total_sum = 0

        def dfs(depth: int, position: int, current_sum: int) -> None:
            nonlocal total_sum

            key = depth * 10 + position
            current_sum += nodes[key]

            left_key = (depth + 1) * 10 + (2 * position - 1)
            right_key = (depth + 1) * 10 + (2 * position)

            has_left = left_key in nodes
            has_right = right_key in nodes

            if not has_left and not has_right:
                total_sum += current_sum
                return

            if has_left:
                dfs(depth + 1, 2 * position - 1, current_sum)

            if has_right:
                dfs(depth + 1, 2 * position, current_sum)

        root_depth = nums[0] // 100
        root_position = (nums[0] // 10) % 10

        dfs(root_depth, root_position, 0)

        return total_sum

The implementation begins by parsing each encoded integer and storing it in a dictionary for constant-time access. The dictionary key combines depth and position into a compact identifier.

The DFS function accumulates the running path sum while traversing downward through the tree. Instead of using actual tree node references, the function computes child coordinates mathematically using the full binary tree indexing rules.

Leaf detection happens when neither computed child key exists in the dictionary. At that point, the accumulated path sum is added to the global answer.

Because the recursion only visits existing nodes, the traversal remains efficient and clean.

Go Solution

func pathSum(nums []int) int {
	nodes := make(map[int]int)

	for _, num := range nums {
		depth := num / 100
		position := (num / 10) % 10
		value := num % 10

		key := depth*10 + position
		nodes[key] = value
	}

	totalSum := 0

	var dfs func(depth int, position int, currentSum int)

	dfs = func(depth int, position int, currentSum int) {
		key := depth*10 + position
		currentSum += nodes[key]

		leftKey := (depth+1)*10 + (2*position - 1)
		rightKey := (depth+1)*10 + (2 * position)

		_, hasLeft := nodes[leftKey]
		_, hasRight := nodes[rightKey]

		if !hasLeft && !hasRight {
			totalSum += currentSum
			return
		}

		if hasLeft {
			dfs(depth+1, 2*position-1, currentSum)
		}

		if hasRight {
			dfs(depth+1, 2*position, currentSum)
		}
	}

	rootDepth := nums[0] / 100
	rootPosition := (nums[0] / 10) % 10

	dfs(rootDepth, rootPosition, 0)

	return totalSum
}

The Go implementation follows the same structure as the Python version. A map[int]int is used for node lookup. Recursive DFS is implemented using a function variable because Go requires explicit declaration for recursive anonymous functions.

There are no concerns about integer overflow because the maximum possible path sum is very small under the given constraints.

Go maps return a second boolean value indicating existence, which makes leaf detection straightforward.

Worked Examples

Example 1

Input:

nums = [113, 215, 221]

Encoded nodes:

Number Depth Position Value
113 1 1 3
215 2 1 5
221 2 2 1

Constructed map:

Key Value
11 3
21 5
22 1

Start DFS from (1,1).

Step Node Current Sum Children Exist? Action
1 11 3 Yes Continue
2 21 8 No Add 8
3 22 4 No Add 4

Final answer:

8 + 4 = 12

Example 2

Input:

nums = [113, 221]

Encoded nodes:

Number Depth Position Value
113 1 1 3
221 2 2 1

Constructed map:

Key Value
11 3
22 1

DFS traversal:

Step Node Current Sum Children Exist? Action
1 11 3 Right child only Continue
2 22 4 No Add 4

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is inserted once and visited once during DFS
Space O(n) The hash map stores all nodes and recursion stack uses additional space

The algorithm performs a single pass to build the hash map and another traversal that visits each node exactly once. Since every operation inside DFS is constant time, the total runtime is linear in the number of nodes.

The space usage is also linear because the hash map stores one entry per node. The recursion depth is at most 4, so stack usage is effectively constant under the given constraints.

Test Cases

from typing import List

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

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

            nodes[depth * 10 + position] = value

        total = 0

        def dfs(depth: int, position: int, current_sum: int) -> None:
            nonlocal total

            key = depth * 10 + position
            current_sum += nodes[key]

            left_key = (depth + 1) * 10 + (2 * position - 1)
            right_key = (depth + 1) * 10 + (2 * position)

            has_left = left_key in nodes
            has_right = right_key in nodes

            if not has_left and not has_right:
                total += current_sum
                return

            if has_left:
                dfs(depth + 1, 2 * position - 1, current_sum)

            if has_right:
                dfs(depth + 1, 2 * position, current_sum)

        dfs(nums[0] // 100, (nums[0] // 10) % 10, 0)

        return total

solution = Solution()

assert solution.pathSum([113, 215, 221]) == 12  # Example 1
assert solution.pathSum([113, 221]) == 4  # Example 2

assert solution.pathSum([111]) == 1  # Single root node
assert solution.pathSum([115]) == 5  # Single node with larger value

assert solution.pathSum([113, 215]) == 8  # Root with only left child
assert solution.pathSum([113, 221]) == 4  # Root with only right child

assert solution.pathSum([113, 215, 221, 315, 331]) == 20  # Multiple leaves

assert solution.pathSum([111, 217, 221, 315, 415]) == 15  # Deeper left-heavy tree

assert solution.pathSum([114, 225, 337, 349]) == 20  # Sparse tree positions
Test Why
[113, 215, 221] Validates standard multi-path case
[113, 221] Validates missing left child handling
[111] Tests single-node tree
[115] Tests single root with larger value
[113, 215] Tests only-left-child traversal
[113, 221] Tests only-right-child traversal
[113, 215, 221, 315, 331] Tests multiple leaves at deeper levels
[111, 217, 221, 315, 415] Tests deeper recursion
[114, 225, 337, 349] Tests sparse position encoding

Edge Cases

Single Node Tree

A tree may contain only one node, such as:

[111]

In this situation, the root is also a leaf. A common bug is forgetting that a node with no children should immediately contribute its path sum. The implementation handles this naturally because both child lookups fail, causing the DFS to treat the root as a leaf.

Missing Left or Right Child

The tree is not necessarily complete. A node may have only one child:

[113, 221]

Here, the root has only a right child. Incorrect implementations sometimes assume that children exist in pairs or rely on array indexing. This solution avoids that issue by checking child existence independently through hash map lookups.

Sparse Position Values

Positions correspond to a full binary tree layout, not compact indexing. That means positions can skip values:

[114, 225, 337]

A naive implementation that tries to reconstruct the tree using contiguous arrays may fail because logical positions do not match storage positions. The hash map approach correctly handles sparse layouts because node relationships are computed mathematically from depth and position rather than physical array placement.