Skip to main content
Talentd

Path Sum IV - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableTreeDepth-First Search5 min readAsked at: Alibaba
Practice this problem

Problem Statement

If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. You are given an ascending array nums consisting of three-digit integers representing a binary tree with a depth smaller than 5, where for each integer:

  • The hundreds digit represents the depth d of this node, where 1 <= d <= 4.
  • The tens digit represents the position p of this node within its level, where 1 <= p <= 8, corresponding to its position in a full binary tree.
  • The units digit represents the value v of this node, where 0 <= v <= 9.

Return the sum of all paths from the root towards the leaves.

It is guaranteed that the given array represents a valid connected binary tree.

 

Example 1:

Input: nums = [113,215,221]

Output: 12

Explanation:

The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: nums = [113,221]

Output: 4

Explanation:

The tree that the list represents is shown. 
The path sum is (3 + 1) = 4.

 

Constraints:

  • 1 <= nums.length <= 15
  • 110 <= nums[i] <= 489
  • nums represents a valid binary tree with depth less than 5.
  • nums is sorted in ascending order.

Approach Overview

Problem Overview: The input represents a binary tree using three-digit integers where the hundreds digit is the depth, the tens digit is the position within that level, and the units digit is the node value. Your task is to reconstruct the structure logically and compute the total of all root‑to‑leaf path sums.

Approach 1: Build the Binary Tree then DFS (O(n) time, O(n) space)

A straightforward method is to explicitly build the tree structure first. Parse each number to extract depth, position, and value, then map each node to its parent using the rule that a node at (d, p) has a parent at (d-1, (p+1)//2). Once the structure is built, run a standard Depth-First Search from the root, accumulating path sums until reaching leaf nodes. Each leaf contributes its path total to the final answer. This approach mirrors how you normally solve path sum problems on a Binary Tree, making it easy to reason about during implementation.

Approach 2: Hash Map + Implicit DFS (O(n) time, O(n) space)

A more efficient approach avoids building the full tree. Store each node in a Hash Table using a key like depth * 10 + position. Then run DFS starting from the root (depth 1, position 1). For each node, compute the keys of its potential children: left child at (d+1, 2p-1) and right child at (d+1, 2p). If neither child exists in the map, the node is a leaf and the current path sum gets added to the result. Otherwise, continue DFS with the updated sum. This method leverages the encoded structure directly and avoids explicit node objects.

The key insight is that the position encoding uniquely determines parent‑child relationships. Because each node can be found with a constant‑time hash lookup, the traversal runs in linear time relative to the number of encoded nodes.

Recommended for interviews: The hash map + implicit DFS approach. It demonstrates that you understand how the positional encoding works and can reconstruct relationships without building a full tree. Mentioning the explicit tree construction approach first can show baseline understanding, but the optimized DFS with hash lookups shows stronger problem‑solving ability.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Build Tree then DFSO(n)O(n)When you want a clear tree structure and standard DFS traversal
Hash Map + Implicit DFSO(n)O(n)General case; avoids building the tree and uses constant-time lookups

Video Solution

Leetcode 666 path sum 4 • DayDay-UpUp • 641 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Path Sum IV easy or hard?
Path Sum IV is generally classified as a Medium problem. The DFS traversal itself is simple, but recognizing how the depth-position encoding determines parent-child relationships is the main challenge.
Path Sum IV Python/Java solution
Implement a hash map where the key represents depth and position and the value is the node value. Run DFS from the root, compute child positions, and accumulate sums until reaching leaves. The same logic works across Python, Java, C++, and Go with O(n) complexity.
How to solve Path Sum IV in O(n)?
Insert each encoded node into a hash map keyed by depth and position. Start DFS from the root and compute child keys using the positional relationship (left: 2p-1, right: 2p). When a node has no children in the map, treat it as a leaf and add the accumulated path sum to the result.
What is the best approach for Path Sum IV?
The hash map with implicit DFS traversal is the most effective approach. Store nodes using a key derived from depth and position, then perform DFS while computing path sums. Child nodes can be located with constant-time hash lookups, producing an O(n) time solution.
Is Path Sum IV asked at Google/Amazon/Meta?
Tree traversal and path sum variations frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact encoding format is less common, the underlying concepts—DFS traversal and tree reconstruction—are common interview topics.
What data structure is used in Path Sum IV?
The solution typically uses a hash table to map encoded node positions to values. Depth-first search is then applied to simulate traversal of the binary tree structure derived from the encoded positions.
What is the time complexity of Path Sum IV?
The optimal solution runs in O(n) time where n is the number of encoded nodes. Each node is inserted into a hash map once and visited once during DFS traversal. Space complexity is also O(n) due to the hash table and recursion stack.

Ready to solve this problem?

Practice Path Sum IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Maximum Path Sum

Next

Path Sum