Path Sum

📋

Path Sum

Edge cases:

</>

IDE

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:public boolean hasPathSum(TreeNode root, int targetSum)bool hasPathSum(TreeNode* root, int targetSum)function hasPathSum(root, targetSum)

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool hasPathSum(TreeNode* root, int targetSum) {
    // Write your solution here
    return false;
}

function hasPathSum(root, targetSum) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for input with no root-to-leaf path summing to targetSumNot checking if node is leaf before comparing sum, allowing partial paths to count.✅ Add condition to check if node.left == null and node.right == null before comparing sum to targetSum.

Wrong: false for input where path sum exists with negative valuesIncorrect sum accumulation ignoring negative values or early pruning.✅ Accumulate sums correctly including negative values; do not prune paths prematurely.

Wrong: true for input where greedy picks largest child first but no valid pathUsing greedy approach instead of exploring all paths.✅ Use full DFS traversal exploring both left and right children regardless of values.

Wrong: true for empty tree inputNot handling null root case properly.✅ Return false immediately if root is null.

Wrong: TLE on large inputExponential recursion or repeated work without pruning.✅ Implement O(n) DFS with early stopping and no repeated computations.

✓

Test Cases

Focus on handling empty trees and single-node trees correctly.

Think about common algorithmic traps like greedy and partial path sums.

Optimize your solution to run in linear time with efficient DFS.

t1_01basic

Input{"root":[5,4,8,11,null,13,4,7,2,null,null,null,1],"targetSum":22}

Expectedtrue

⏱ Performance - must finish in 2000ms

The path 5->4->11->2 sums to 22.

💡 Think about traversing from root to leaves and accumulating sums.

💡 Use DFS to explore all root-to-leaf paths and check sums.

💡 Return true if any leaf path sum equals targetSum.

Why it failed: Failed basic case: likely not checking leaf nodes correctly or sum accumulation is wrong. Fix by verifying leaf condition and subtracting node values properly.

✓ Correctly identifies root-to-leaf path sums matching targetSum.

t1_02basic

Input{"root":[1,2,3],"targetSum":5}

Expectedfalse

⏱ Performance - must finish in 2000ms

No root-to-leaf path sums to 5 (paths: 1->2=3, 1->3=4).

💡 Check all root-to-leaf paths and their sums.

💡 Remember to verify leaf nodes only, not intermediate nodes.

💡 Return false if no path matches targetSum.

Why it failed: Incorrectly returns true or misses leaf check. Fix by ensuring only leaf nodes are considered for sum comparison.

✓ Correctly returns false when no path sums to targetSum.

t2_01edge

Input{"root":[],"targetSum":0}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty tree has no paths, so return false.

💡 Consider what happens when the tree is empty (null root).

💡 An empty tree has no root-to-leaf paths.

💡 Return false immediately if root is null.

Why it failed: Fails empty tree case by returning true or error. Fix by adding null root check returning false.

✓ Handles empty tree correctly by returning false.

t2_02edge

Input{"root":[7],"targetSum":7}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node tree where node value equals targetSum returns true.

💡 Check if root is leaf and its value equals targetSum.

💡 Leaf node means no left or right children.

💡 Return true if root.val == targetSum and root is leaf.

Why it failed: Fails single node equal targetSum by not checking leaf condition or value correctly. Fix by adding leaf check and value comparison.

✓ Correctly returns true for single node equal to targetSum.

t2_03edge

Input{"root":[7],"targetSum":10}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single node tree where node value does not equal targetSum returns false.

💡 Verify leaf node value against targetSum.

💡 Return false if root.val != targetSum for leaf node.

💡 Do not consider non-existent children.

Why it failed: Incorrectly returns true or error for single node not matching targetSum. Fix by proper leaf and value check.

✓ Correctly returns false when single node value differs from targetSum.

t2_04edge

Input{"root":[1,-2,-3,1,3,-2,null,-1],"targetSum":-1}

Expectedtrue

⏱ Performance - must finish in 2000ms

Path 1->-2->1->-1 sums to -1, demonstrating negative values handled correctly.

💡 Ensure negative values are correctly added/subtracted in sum.

💡 DFS must handle negative node values properly.

💡 Check all root-to-leaf paths including negative values.

Why it failed: Fails negative values by ignoring sign or incorrect sum calculation. Fix by correctly accumulating sums with negatives.

✓ Handles negative values correctly in path sums.

t3_01corner

Input{"root":[1,2,3,4,5,6,7],"targetSum":10}

Expectedfalse

⏱ Performance - must finish in 2000ms

No root-to-leaf path sums to 10; tests greedy approach that picks largest child first.

💡 Greedy approach picking largest child first may fail here.

💡 Must explore all paths, not just the largest values.

💡 Use full DFS to check every root-to-leaf path sum.

Why it failed: Fails greedy trap by returning true incorrectly. Fix by exploring all paths instead of greedy selection.

✓ Correctly rejects greedy trap by exhaustive path checking.

t3_02corner

Input{"root":[1,2],"targetSum":1}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tests confusion between root-to-leaf and root-to-any-node path sums; only leaf paths count.

💡 Only root-to-leaf paths count, not partial paths.

💡 Check if node is leaf before comparing sum.

💡 Return false if no leaf path matches targetSum.

Why it failed: Mistakes root-to-any-node path for root-to-leaf, returning true incorrectly. Fix by verifying leaf nodes only.

✓ Correctly distinguishes root-to-leaf paths from partial paths.

t3_03corner

Input{"root":[1,2,null,3,null,4,null,5],"targetSum":15}

Expectedtrue

⏱ Performance - must finish in 2000ms

Deep unbalanced tree tests stack overflow or incorrect recursion termination.

💡 Ensure recursion handles deep unbalanced trees.

💡 Check base case for leaf nodes correctly.

💡 Accumulate sums properly through all levels.

Why it failed: Fails deep recursion or incorrect base case, causing wrong output or crash. Fix by proper leaf check and recursion termination.

✓ Handles deep unbalanced trees correctly.

t4_01performance

Input{"root":[1,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1],"right":null}

Expectednull

⏱ Performance - must finish in 2000ms

Deep left-skewed tree with 100000 nodes; O(n) DFS must complete within 2 seconds.

💡 Use DFS with early stopping to avoid unnecessary traversal.

💡 Avoid recomputing sums; carry running sum in recursion.

💡 Iterative DFS with stack can also be efficient.

Why it failed: TLE due to exponential or repeated work. Fix by using O(n) DFS with pruning and no repeated computations.

✓ Efficient O(n) DFS confirmed by passing performance test.

Practice

1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?

easy

A. Postorder traversal using two stacks

B. Level-order traversal using a queue

C. Morris preorder traversal using threaded binary tree

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirement

   The problem requires visiting root before left and right subtrees, which is preorder traversal.

2. Step 2: Identify approach with no extra space

   Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preorder visits root first; Morris traversal achieves this with O(1) space [OK]

Hint: Preorder visits root before children [OK]

Common Mistakes:

• Confusing inorder or postorder with preorder traversal
• Assuming recursion is always needed
• Using level-order which visits nodes by depth

2. You are given a binary tree and need to find the longest path from the root node down to the farthest leaf node. Which algorithmic approach guarantees an optimal solution to determine this maximum depth?

easy

A. Dynamic Programming with memoization on node values

B. Greedy traversal picking the first child node at each step

C. Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all nodes

D. Sorting nodes by value and selecting the deepest node

Solution

1. Step 1: Understand the problem requires exploring all paths from root to leaves

   Finding maximum depth means checking every path from root to leaves, so partial or greedy approaches won't guarantee correctness.

2. Step 2: Identify algorithms that explore all nodes

   DFS or BFS traverse all nodes systematically, ensuring the maximum depth is found. Greedy or sorting approaches do not consider all paths.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DFS and BFS both visit all nodes to find max depth [OK]

Hint: Max depth requires full traversal, not greedy or sorting [OK]

Common Mistakes:

• Assuming greedy traversal finds max depth
• Confusing max depth with max node value
• Thinking sorting nodes helps depth calculation

3. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?

medium

A. Line creating root node with postorder[-1]

B. Line initializing inorder_index to 0

C. Line attaching node as right child

D. Line popping from stack inside while loop

Solution

1. Step 1: Identify inorder_index initialization

   inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.

2. Step 2: Consequences of wrong initialization

   Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct inorder_index initialization is critical for stack popping logic [OK]

Hint: inorder_index must start at last index, not zero [OK]

Common Mistakes:

• Wrong inorder_index initialization
• Confusing postorder traversal direction
• Incorrect stack popping conditions

4. Suppose the problem is modified so that node values can be negative, and you want to find all root-to-leaf paths summing to targetSum. Which modification to the DFS approach is necessary to ensure correctness?

hard

A. Remove pruning and explore all paths fully since negative values can reduce sums

B. Add pruning to stop exploring paths when current_sum exceeds targetSum

C. Use BFS instead of DFS to avoid infinite loops caused by negative values

D. Sort children nodes by value to explore promising paths first

Solution

1. Step 1: Understand effect of negative values

   Negative values can decrease current_sum, so pruning based on exceeding targetSum can miss valid paths.

2. Step 2: Adjust DFS to remove pruning

   To ensure all valid paths are found, pruning must be removed and all paths fully explored.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Pruning breaks correctness with negative values; full exploration needed [OK]

Hint: Negative values invalidate pruning based on sum limits [OK]

Common Mistakes:

• Applying pruning blindly
• Switching to BFS unnecessarily

5. Suppose the problem is modified so that node values can be negative integers, and the goal remains to sum all root-to-leaf numbers formed by concatenation (including negative signs). Which of the following changes to the algorithm is necessary to handle this correctly?

hard

A. Skip negative nodes since they break number formation

B. Continue using integer arithmetic with multiplication by 10, ignoring signs

C. Add absolute values of node.val to current_number to avoid sign issues

D. Use string concatenation of node values along the path and convert to integer at leaf nodes

Solution

1. Step 1: Understand impact of negative values

   Integer arithmetic with multiplication by 10 assumes digits 0-9; negative signs break this assumption.

2. Step 2: Identify correct approach

   Concatenating node values as strings preserves negative signs and digit order; convert to integer only at leaf nodes.

3. Step 3: Confirm other options fail

   Ignoring signs or skipping negatives leads to incorrect sums or incomplete paths.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   String concatenation handles negative digits correctly [OK]

Hint: Use string concatenation for negative digits [OK]

Common Mistakes:

• Assuming all digits are positive
• Using arithmetic without sign handling