Path Sum IV — LeetCode 666 Encoded Tree DFS

Problem Statement#

You are given an integer array nums of three-digit integers representing a binary tree of depth at most 4. For each integer abc:

• The hundreds digit a is the depth D (1-indexed, 1..4).
• The tens digit b is the position P at level D (1-indexed, 1..2^(D-1)).
• The ones digit c is the node value (1..9).

Return the sum of all paths from the root toward any leaf.

Constraints:

• 1 <= nums.length <= 15
• All elements in nums are unique
• 1 <= nums[i] <= 999
• nums represents a valid binary tree

Input:  nums = [113,215,221]
Output: 12

Input:  nums = [113,221]
Output: 4

Why This Problem Matters#

LeetCode 666 — Path Sum IV — is an Amazon, Google, and Alibaba favorite that tests whether candidates can decode a custom representation, build a virtual tree, and run a DFS path sum on it. The clever encoding abc = depth * 100 + position * 10 + value mirrors real-world serialization formats (heap-array indexing, tile coordinates, sparse trees in databases).

Many candidates over-engineer it by physically building TreeNode objects. The cleaner answer uses a hashmap keyed by (depth, position) and computes child positions via (depth+1, 2*position - 1) for left and (depth+1, 2*position) for right — a heap-style coordinate trick.

This problem is a Google L4 favorite for testing "model the data correctly" instincts and the depth-position arithmetic that powers segment trees and Fenwick trees.

The Core Insight#

Treat the tree as a hashmap from coordinate (depth, position) to value. Children are computed via:

• Left child: (depth+1, 2*position - 1)
• Right child: (depth+1, 2*position)

DFS from the root (1, 1). Carry a running path sum; when both children are absent, add the running sum to the global answer.

This avoids ever constructing TreeNode objects and runs in O(n) since each entry is visited exactly once.

Visual Dry Run#

nums = [113, 215, 221]:

• 113 -> depth 1, pos 1, value 3 (root)
• 215 -> depth 2, pos 1, value 5 (left child of root)
• 221 -> depth 2, pos 2, value 1 (right child of root)

Total: 12.

Solution (Optimal)#

from typing import List
 
class Solution:
    def pathSum(self, nums: List[int]) -> int:
        tree = {}
        for num in nums:
            depth = num // 100
            pos = (num // 10) % 10
            value = num % 10
            tree[(depth, pos)] = value
 
        total = [0]
 
        def dfs(depth: int, pos: int, running: int) -> None:
            if (depth, pos) not in tree:
                return
            running += tree[(depth, pos)]
            left_key = (depth + 1, 2 * pos - 1)
            right_key = (depth + 1, 2 * pos)
            if left_key not in tree and right_key not in tree:
                total[0] += running
                return
            dfs(depth + 1, 2 * pos - 1, running)
            dfs(depth + 1, 2 * pos, running)
 
        dfs(1, 1, 0)
        return total[0]

var pathSum = function(nums) {
    const tree = new Map();
    for (const num of nums) {
        const depth = Math.floor(num / 100);
        const pos = Math.floor(num / 10) % 10;
        const value = num % 10;
        tree.set(`${depth},${pos}`, value);
    }
    let total = 0;
    const dfs = (depth, pos, running) => {
        const key = `${depth},${pos}`;
        if (!tree.has(key)) return;
        running += tree.get(key);
        const leftKey = `${depth + 1},${2 * pos - 1}`;
        const rightKey = `${depth + 1},${2 * pos}`;
        if (!tree.has(leftKey) && !tree.has(rightKey)) {
            total += running;
            return;
        }
        dfs(depth + 1, 2 * pos - 1, running);
        dfs(depth + 1, 2 * pos, running);
    };
    dfs(1, 1, 0);
    return total;
};

Time: O(n) — one pass to build the map plus DFS visits each node once. Space: O(n) — hashmap and recursion stack at depth at most 4.

Common Mistakes#

• Building TreeNode structures unnecessarily — wastes time and memory.
• Wrong child arithmetic: (depth+1, 2*position) and (depth+1, 2*position + 1) is the array-heap index; this problem uses 1-indexed positions with 2*p - 1 and 2*p.
• Forgetting the leaf condition: a node with no children of its coordinate must also lack any child coordinate in the map.
• Using int(str(num)) parsing instead of arithmetic — slower and more fragile.
• Returning the running sum instead of accumulating into a global, missing some leaves on multi-leaf trees.

Interview Tips#

• State the encoding aloud: hundreds, tens, ones.
• Mention the heap-style coordinate trick: it generalizes to any binary tree stored as (depth, pos).
• Walk through one decode and one DFS step before coding.
• Note that depth is bounded by 4, so recursion is shallow and a stack-based DFS is unnecessary.

Follow-up Questions#

• "Generalize to depth > 9" — Use a different encoding (tuples or strings) so values do not overflow a digit.
• "Return the path with maximum sum" — Track per-leaf sums and pick max.
• "Count distinct paths summing to target" — Add a hashmap of running sums during DFS (LC 437 style).
• "Build the actual tree from the encoding" — Iterate and link parents to children using the coordinate map.
• "Print the tree pretty" — Recurse with indentation per depth.

Key Takeaways#

• LeetCode 666 Path Sum IV decodes integers into (depth, position, value) triples and runs DFS on a virtual tree.
• Children are computed by (depth+1, 2*pos-1) for left and (depth+1, 2*pos) for right.
• Time and space are O(n); depth is at most 4.
• A hashmap representation avoids constructing TreeNode objects.
• Asked at Amazon, Google, and Alibaba as a "model the data" tree exercise.
• The position arithmetic mirrors heap-array indexing in segment trees.
• Path sum accumulation pairs perfectly with the leaf check (no child coord present).