How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Find the Shortest Target-Sum Path | Citadel Coding Question

Find the Shortest Target-Sum Path

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given the root of a binary tree and an integer `targetSum`, find a root-to-leaf path whose node values add up to `targetSum`. Return the path as a list of node values. If multiple valid paths exist, return one with the minimum number of nodes. If no such path exists, return an empty list. A leaf is a node with no children. Example: ```text Input: 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 targetSum = 22 Output: [5, 4, 11, 2] ``` The returned path starts at the root, ends at a leaf, and its values sum to `22`.

Quick Answer: This question evaluates skills in binary tree traversal, path-sum computation, and optimization for selecting a root-to-leaf path with the minimal number of nodes.

You are given a binary tree and an integer `targetSum`. Find a root-to-leaf path whose node values add up to `targetSum`. Return the path as a list of node values. If multiple valid paths exist, return one with the minimum number of nodes. If no such path exists, return an empty list. A leaf is a node with no children. For this problem, the binary tree is provided as a level-order list, where `None` represents a missing child. Example: Tree: `[5,4,8,11,None,13,4,7,2,None,None,None,1]` `targetSum = 22` Output: `[5, 4, 11, 2]`

Constraints

0 <= number of nodes <= 10^4
-10^4 <= node values <= 10^4
-10^9 <= targetSum <= 10^9
The tree is given in level-order form, using None for missing children

Examples

Input: ([5,4,8,11,None,13,4,7,2,None,None,None,1], 22)

Expected Output: [5, 4, 11, 2]

Explanation: The path 5 -> 4 -> 11 -> 2 is a root-to-leaf path and its sum is 22.

Input: ([], 0)

Expected Output: []

Explanation: An empty tree has no root-to-leaf paths.

Input: ([7], 7)

Expected Output: [7]

Explanation: The single node is also a leaf, and its value matches the target sum.

Input: ([1,2,3,None,None,-1,4], 3)

Expected Output: [1, 2]

Explanation: There are two valid paths: [1, 2] and [1, 3, -1]. The shorter one is [1, 2].

Input: ([1,2,3], 5)

Expected Output: []

Explanation: The root-to-leaf sums are 3 and 4, so no valid path exists.

Input: ([1,1,1,1,None,None,1], 3)

Expected Output: [1, 1, 1]

Explanation: There are multiple shortest valid paths with the same values. Returning [1, 1, 1] is correct.

Hints

Traverse the tree while keeping track of both the current sum and the current path.
Only root-to-leaf paths are valid. When you reach a leaf with the correct sum, compare its path length with the best answer found so far.

Quick Overview

This question evaluates skills in binary tree traversal, path-sum computation, and optimization for selecting a root-to-leaf path with the minimal number of nodes.