Minimum Length Root to Leaf BST Path for Given Sum

Problem

Given a binary search tree, find the minimum length (number of nodes) of a root-to-leaf path whose sum equals a given target value target OR S. If no such path exists, return a special value (e.g., infinity or null).

Examples

Example 1

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

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 – DFS (with BST Pruning)

We use DFS to find the minimum length root-to-leaf path whose sum equals the target. For a Binary Search Tree (BST), we can prune the search space:

Intuition

Suppose we have the following BST:

    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 minimum length 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].

This approach uses the BST property to prune unnecessary searches, always trying the most promising direction first.

Approach

1. At each node, subtract the node's value from the remaining sum (e.g., rem = target - node.val).
2. If the node is a leaf and the remaining sum is 0, we've found a valid path.
3. If the remaining sum is less than or equal to the node's value (i.e., rem <= node.val), search left first (since left children are smaller); if not found, search right.
4. If the remaining sum is greater (i.e., rem > node.val), search right first; if not found, search left.
5. Only search both sides if necessary, to minimize path length.
6. Return the minimum length found, or -1 if no path exists.

Code

C++

// Returns the minimum length of a root-to-leaf path with given sum in a BST, or INT_MAX if none exists
class Solution {
public:
  int minLenSumPathBST(TreeNode* root, int sum) {
    return dfs(root, sum, 0);
  }
private:
  int dfs(TreeNode* node, int sum, int len) {
    if (!node) return INT_MAX;
    int rem = sum - node->val;
    // If leaf and sum matches, return path length
    if (!node->left && !node->right && rem == 0) return len + 1;
    int l = INT_MAX;
    // Prune: search left first if rem <= node value
    if (rem <= node->val) {
      l = dfs(node->left, rem, len + 1);
      if (l == INT_MAX) l = dfs(node->right, rem, len + 1);
    } else {
      l = dfs(node->right, rem, len + 1);
      if (l == INT_MAX) l = dfs(node->left, rem, len + 1);
    }
    return l;
  }
};

Java

// Returns the minimum length of a root-to-leaf path with given sum in a BST, or Integer.MAX_VALUE if none exists

class Solution {
  public int minLenSumPathBST(TreeNode root, int target) {
    return dfs(root, target, 0);
  }
  private int dfs(TreeNode node, int target, int len) {
    if (node == null) return Integer.MAX_VALUE;
    int rem = target - node.val;
    // If leaf and sum matches, return path length
    if (node.left == null && node.right == null && rem == 0) return len + 1;
    int l = Integer.MAX_VALUE;
    // Prune: search left first if rem <= node value
    if (rem <= node.val) {
      l = dfs(node.left, rem, len + 1);
      if (l == Integer.MAX_VALUE) l = dfs(node.right, rem, len + 1);
    } else {
      l = dfs(node.right, rem, len + 1);
      if (l == Integer.MAX_VALUE) l = dfs(node.left, rem, len + 1);
    }
    return l;
  }
}

Python

# Returns the minimum length of a root-to-leaf path with given sum in a BST, or -1 if none exists

class Solution:
  def minLenSumPathBST(self, root, target):
    def dfs(node, rem, length):
      if not node:
        return float('inf')
      rem -= node.val
      # If leaf and sum matches, return path length
      if not node.left and not node.right and rem == 0:
        return length + 1
      ans = float('inf')
      # Prune: search left first if rem <= node value
      if rem <= node.val:
        ans = dfs(node.left, rem, length + 1)
        if ans == float('inf'):
          ans = dfs(node.right, rem, length + 1)
      else:
        ans = dfs(node.right, rem, length + 1)
        if ans == float('inf'):
          ans = dfs(node.left, rem, length + 1)
      return ans
    ans = dfs(root, target, 0)
    return ans if ans != float('inf') else -1

Complexity

• ⏰ Time complexity: O(log n) on average for balanced BST, O(n) worst case.
• 🧺 Space complexity: O(h), where h is the height of the tree (due to recursion stack).