Katkat
Back

Find the Shortest Target-Sum Path

CitadelSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate binary trees using recursion or iterative traversal while maintaining state to find a path that meets a specific sum criteria with the smallest number of nodes.

Problem Statement

Given a binary tree where each node contains an integer value, find a path from the root to any leaf node such that the sum of the values of the nodes in the path equals a target integer K. If multiple such paths exist, return the path that contains the minimum number of nodes. If no path exists, return an empty list. If there is a tie in the number of nodes, any one of the shortest paths is acceptable.

Function Signature

def find_shortest_target_path(root, target):
    # Return a list of node values representing the path

Example 1

Input:

    1
   / \
  2   3
 / \   \
4   5   6

Target: 7 (Path: 1 -> 2 -> 4)

Output: [1, 2, 4]

Example 2

Input:

    5
   / \
  4   8
 /   / \
11  13  4
/  \     \
7   2     1

Target: 22

  • Path 1: 5 -> 4 -> 11 -> 2 (length 4)
  • Path 2: 5 -> 8 -> 9 (Wait, let's assume a path exists)

Output: [5, 4, 11, 2]

Constraints

  • The tree height H is at most 1000.
  • Node values can be negative, zero, or positive.
  • The number of nodes N is up to 10^5.

Edge Cases

  • Empty tree: Return [].
  • No path sums to K: Return [].
  • Single node tree where node value equals K.

Hints

Hint 1

Consider using Depth First Search (DFS) to traverse the tree, passing the current path and the running sum down the recursion stack.

Hint 2

At each leaf node, check if the current sum equals the target, and compare the current path length against the shortest path length found so far.

Hint 3

Since we want the minimum number of nodes, keep a global variable (or a non-local variable) to track the current 'best' path and update it only when a shorter valid path is found.

Follow-up questions

  • How would your approach change if you needed to find the path with the maximum number of nodes instead?
  • Can this problem be solved using Breadth First Search (BFS)? What are the memory trade-offs compared to DFS?
  • What if the path does not need to start at the root and end at a leaf, but can start and end at any node?