EasyTreesAI interview only
Path Sum
Asked atamazonmicrosoftmetagooglebloomberg
01 · Problem
Given the root of a binary tree and an integer targetSum, return true if there is a path from the root down to a leaf whose node values add up to exactly targetSum, and false otherwise.
A leaf is a node with no children. The tree is given in level-order, with null marking a missing child. An empty tree has no root-to-leaf paths, so the answer is false for any targetSum.
02 · Examples
Example 01
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1Input
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output
true
The path 5 -> 4 -> 11 -> 2 sums to 22.
Example 02
Input
root = [1,2,3], targetSum = 5
Output
false
The two root-to-leaf paths sum to 3 (1 -> 2) and 4 (1 -> 3); neither is 5.
Example 03
Input
root = [], targetSum = 0
Output
false
An empty tree has no root-to-leaf path, even for a target of 0.
03 · Constraints
- 01The number of nodes in the tree is in the range [0, 100].
- 02-1000 <= Node.val <= 1000
- 03-1000 <= targetSum <= 1000
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.