MiddleCodeCommonNot answered yet
Find a root-to-leaf path in a binary tree with a given sum
Given a binary tree and a target sum, return the nodes of one root-to-leaf path whose values add up to the target, or an empty path if none exists.
Requirements:
- The path must start at the root and end at a leaf.
- Values may be negative; clarify this before coding.
struct Node { Node* left; Node* right; int val; };
std::vector<Node*> findPath(Node* root, int target) {
// your code here
}Write the implementation.
Run a DFS carrying the remaining sum and the current path. At each node subtract its value; at a leaf, accept the path iff the remaining sum is now zero. Recurse into children, pushing the node before and popping after (backtracking). Return the first accepted path. O(n) time.
- ✗Accepting at an internal node instead of requiring a leaf endpoint
- ✗Assuming all values are positive and pruning negative branches
- ✗Forgetting to pop the node on backtracking, leaking it into the wrong path
- →How does allowing negative values rule out the early-stop pruning?
- →How would you return all such paths instead of the first one?
Contents
Task
Return one root-to-leaf path with a given value sum; values may be negative.
Solution
#include <vector>
struct Node { Node* left; Node* right; int val; };
static bool dfs(Node* n, int rem, std::vector<Node*>& path) {
if (!n) return false;
path.push_back(n);
rem -= n->val;
if (!n->left && !n->right && rem == 0) return true; // leaf and sum matched
if (dfs(n->left, rem, path) || dfs(n->right, rem, path)) return true;
path.pop_back(); // backtrack
return false;
}
std::vector<Node*> findPath(Node* root, int target) {
std::vector<Node*> path;
dfs(root, target, path);
return path;
}Key points
- Accept only at a leaf with zero remainder, never at an internal node.
- Negative values forbid early pruning — explore both branches.
push_backbefore descending andpop_backafter is correct backtracking.
Contents
