Home > Reflections | ⏮️ ⏭️

2024-08-01

🏋 Coding Practice

112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.

🪞 Reflections

1. Never great to get a wrong submission
   1. This was due to a misunderstanding of the problem.
   2. A careless mistake - I should read the description more carefully.
   3. My initial implementation did what I wanted it to - just not what the problem was looking for.
   4. This highlights the importance of asking clarifying questions during a real interview
2. Finding my way back to a working solution in under 25 minutes isn’t terrible
3. The initial implementation came out quickly and without much waffling or difficulty
4. Manual testing
   1. I added the null-checks as I wrote the initial code, which feels more efficient than coming back afterword
   2. while my tree notation for test values isn’t hyper-efficient, it’s much easier to work with than the super efficient, but easy to misread list annotation used in LeetCode examples (e.g. [1,2,3,null]
   3. Testing the recursive implementation felt natural and effective
5. All in all, a nice warm up for my real interview later today
   1. I intentionally chose an Easy LeetCode problem just to warm up my usual routine without inducing too much stress by struggling with a more challenging problem on the day of an interview.

⌨️ My Solution

/* Determine if a root-to-leaf path summing to target exists  
Thoughts  
1. In the worst case, we have to traverse the entire tree  
2. But there's a lot of overlap in the paths  
3. Depth first search seems appropriate so we can stop as soon as we get a match  
4. Trees are recursive data structures - a recursive algorithm feels appropriate  
  
Plan:  
1. Implement a recursive depth first search  
  2. maintain a path-prefix sum until reaching each leaf  
  3. return the OR (lazily if possible) of the boolean response of each child  
  4. micro-optimization: if there are no negative values, we could abandon a sub-tree when we surpass the target  
    - note: negative values are possible, so we can't abandon early  
  
[4:20] Done planning  
[9:16] Done with initial implementation  
[15:04] Done with test  
[16:05] Initial Submission  
Bug found after submission  
1. Wrong Answer -> [], 0 (expected false, yielded true)  
  - Okay, I guess the empty sum in this case isn't zero; should have been a clarifying question  
[18:30] fixed above  
[18:45] Next submission  
Bug found after submission:  
1. Wrong Answer -> [1,2], 1 (expected false, yielded true)  
  - Ah - language from the description: "A leaf is a node with no children"  
  - so don't follow paths to the null  
[24:40] Successful submission  
Oh yeah, this is linear (O(N)) in runtime and extra space complexity  
*/  
  
/**  
 * Definition for a binary tree node.  
 * class TreeNode {  
 *     val: number  
 *     left: TreeNode | null  
 *     right: TreeNode | null  
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {  
 *         this.val = (val===undefined ? 0 : val)  
 *         this.left = (left===undefined ? null : left)  
 *         this.right = (right===undefined ? null : right)  
 *     }  
 * }  
 */  
function hasPathSum(root: TreeNode | null, targetSum: number, prefixSum: number | null = null): boolean { // null,4,4; {v:3},4,1; null, 4, 10; {v:9}, 4, 1; root={v:1,l:{v:9},r:{v:3}} targetSum=4  
  if (!root) return false  
  const newPrefixSum: number = (prefixSum || 0) + root.val // 4; 10; 1; null-check: safe access  
  if (!root.left && !root.right) {  
    return newPrefixSum === targetSum // 4 === 4 => true; 10 !== 4 => false  
  }  
  return (root.left ? hasPathSum(  
    root.left, // null; null; {v:9}; null-check: safe access  
    targetSum, // 4; 4; 4  
    newPrefixSum // 4; 10; 1  
  ) : false) || (root.right ? hasPathSum( // lazy OR for early-returning depth-first search  
    root.right, // {v:3}; null; null-check: safe access  
    targetSum, // 4; 4  
    newPrefixSum // 1; 10  
  ) : false)  
};