Problem

Given a binary tree, find the root-to-leaf path with the minimum length such that the path sum equals a target value S. If no such path exists, return an empty path.

Example 1

graph TD
    E(5)
    E --- D(4) & H(8)
    D --- K(11)
    D ~~~ N1:::hidden 
    H --- M(13) & D2(4)
    K --- G(7) & B(2)
    D2 ~~~ N2:::hidden
    D2 --- A(1)

    linkStyle 0 stroke:#FF0000,stroke-width:2px;
    linkStyle 2 stroke:#FF0000,stroke-width:2px;
    linkStyle 7 stroke:#FF0000,stroke-width:2px;

classDef hidden display:none
  
1
2
3
4
5
6

Binary Tree: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22  
Output: [5,4,11,2]  
Explanation: There are two paths with sum S (22):  
1. Path [5,4,11,2] with length 4  
2. Path [5,8,4,5] with length 4  
Among these, the shortest path is [5,4,11,2].

Example 2

graph TD
    A(8)
    A --- B(4) & C(12)
    B --- D(2) & E(6)
    C --- F(5) & G(14)
    E ~~~ N1:::hidden
    E --- H(7)
    G ~~~ N2:::hidden
    H ~~~ N3:::hidden

    linkStyle 1 stroke:#FF0000,stroke-width:2px;
    linkStyle 4 stroke:#FF0000,stroke-width:2px;


classDef hidden display:none
  
1
2
3
4
5
6

Binary Tree: root = [8,4,12,2,6,10,14,null,null,7,null,5], target = 25
Output: [8,12,5]
Explanation: There are two paths with sum 25:
1. Path [8,4,6,7] with length 4
2. Path [8,12,5] with length 3
So, we choose the path with length 3.

Solution

Method 1 – Using DFS

Intuition (with Example)

Let’s use Example 2:

1
2
3
4
5
6
7

    8
   / \
  4   12
 / \   / \
2   6 5  14
      \
       7

root = [8,4,12,2,6,10,14,null,null,7,null,5], target = 25

We want the shortest root-to-leaf path whose sum is 25.

  • Start at 8, remaining sum is 17.
  • Go right to 12: 17-12=5. Go left to 5: 5-5=0 (leaf). Path [8,12,5] (length 3) is valid.
  • Alternatively, go left from 8 to 4: 17-4=13, right to 6: 13-6=7, right to 7: 7-7=0 (leaf). Path [8,4,6,7] (length 4) is also valid, but longer.
  • So, the shortest path is [8,12,5].

Approach

  1. If root is empty, return an empty list.
  2. Use DFS recursively to traverse the tree.
  3. At each node:
    • Add its value to the current path sum and include it in the current path.
    • If the node is a leaf:
      • If the current path sum equals target and the current path is shorter than the recorded shortest, update the shortest path.
    • Continue DFS for left and right children.
  4. Return the shortest path after DFS.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
    public List<Integer> minimumLengthPath(TreeNode root, int target) {
        List<Integer> result = new ArrayList<>(), currentPath = new ArrayList<>();
        findPath(root, target, 0, currentPath, result);
        return result;
    }

    private void findPath(TreeNode node, int target, int currentSum, List<Integer> currentPath, List<Integer> result) {
        if (node == null) return;

        currentPath.add(node.val);
        currentSum += node.val;

        // Check if we hit a leaf node
        if (node.left == null && node.right == null) {
            if (currentSum == target && (result.isEmpty() || currentPath.size() < result.size())) {
                result.clear();
                result.addAll(new ArrayList<>(currentPath));
            }
        }

        // Recursive DFS
        findPath(node.left, target, currentSum, currentPath, result);
        findPath(node.right, target, currentSum, currentPath, result);

        // Backtrack to explore other paths
        currentPath.remove(currentPath.size() - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def minimumLengthPath(self, root, target):
        result = []
        self.findPath(root, target, 0, [], result)
        return result

    def findPath(self, node, target, currentSum, currentPath, result):
        if not node:
            return

        currentPath.append(node.val)
        currentSum += node.val

        # Check if we hit a leaf node
        if not node.left and not node.right:
            if currentSum == target and (not result or len(currentPath) < len(result)):
                result.clear()
                result.extend(currentPath)

        # Recursive DFS
        self.findPath(node.left, target, currentSum, currentPath, result)
        self.findPath(node.right, target, currentSum, currentPath, result)

        # Backtrack to explore other paths
        currentPath.pop()

Complexity

  • ⏰ Time complexity: O(n) where n is the total number of nodes in the binary tree. Each node is visited once during DFS traversal.
  • 🧺 Space complexity: O(h) where h is the height of the binary tree. This accounts for the recursive stack, which at maximum, will be proportional to the height of the tree.