Path Sum Root to Leaf in Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is null?

Yes→Return false

No↓

Check if leaf node?

Yes→Check if sum equals node value

↓

Return true/false

↓

Subtract node value from sum

↓

Recurse left child

↓

Recurse right child

↓

Return left OR right result

Start from root, check if current node is leaf and sum matches. Otherwise, subtract node value and recurse left and right. Return true if any path matches.

Execution Sample

DSA Typescript

function hasPathSum(node, sum) {
  if (!node) return false;
  if (!node.left && !node.right) return sum === node.val;
  return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Checks if there is a root-to-leaf path with the given sum in the binary tree.

Execution Table

Step	Operation	Current Node	Sum Needed	Leaf?	Return Value	Visual State
1	Start at root	5	22	No	N/A	5 / \ 4 8
2	Recurse left	4	17 (22-5)	No	N/A	4 / 11
3	Recurse left	11	13 (17-4)	No	N/A	11 / 7 2
4	Recurse left	7	2 (13-11)	Yes	False	7
5	Recurse right	2	2 (13-11)	Yes	True	2
6	Return from 11	11	13	No	True	11
7	Return from 4	4	17	No	True	4
8	Recurse right	8	17 (22-5)	No	N/A	8 / 13 4
9	Recurse left	13	9 (17-8)	Yes	False	13
10	Recurse right	4	9 (17-8)	Yes	False	4
11	Return from 8	8	17	No	False	8
12	Return from root	5	22	No	True	5

💡 Returned true at leaf node with path sum matching 22

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	Final
Current Node	5	5	4	11	7	2	11	4	8	13	4	8	5
Sum Needed	22	22	17	13	2	2	13	17	17	9	9	17	22
Return Value	N/A	N/A	N/A	N/A	False	True	True	True	N/A	False	False	False	True

Key Moments - 3 Insights

Why do we check if the node is a leaf before comparing the sum?

Because only root-to-leaf paths count. The check at Step 4 and 5 ensures we only compare sum when at a leaf node, as shown in execution_table rows 4 and 5.

Why do we subtract the node value from sum before recursion?

We reduce the sum needed by the current node's value to check if the remaining path sums to the reduced sum. This is seen in the 'Sum Needed' column changing each step.

What happens if a path returns true early?

The function returns true immediately without checking other paths, as seen at Step 5 returning true and propagating back up in Steps 6 and 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum needed when visiting node 11 at Step 3?

A 13

B 17

C 22

D 2

💡 Hint

Check the 'Sum Needed' column at Step 3 in the execution_table.

At which step does the function first return true?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Return Value' column in execution_table rows 4 and 5.

If the left subtree of node 4 was missing, what would be the return value at Step 7?

A N/A

B False

C Depends on right subtree

D True

💡 Hint

Step 7 return depends on left and right subtree results as per execution_table logic.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root node
- If node is leaf, check sum == node.val
- Else subtract node.val from sum
- Recurse left and right
- Return true if any path matches sum
- Stops early if path found

Full Transcript

This concept checks if a binary tree has a root-to-leaf path where the sum of node values equals a target sum. We start at the root and check if the node is null, returning false if so. If the node is a leaf, we compare the remaining sum with the node's value. If they match, we return true. Otherwise, we subtract the node's value from the sum and recursively check the left and right children. The function returns true if any path matches the sum. The execution table shows each step, the current node, the sum needed, whether the node is a leaf, and the return value. The variable tracker shows how the current node and sum needed change at each step. Key moments clarify why leaf checks happen first, why sum is reduced, and how early returns work. The visual quiz tests understanding of sum values at steps, when true is returned, and how missing subtrees affect results.

Practice

1. What does the "Path Sum Root to Leaf" problem ask you to find in a binary tree?

easy

A. The sum of all node values in the binary tree

B. If there exists a root-to-leaf path with a sum equal to a given target

C. The total number of nodes in the binary tree

D. The maximum depth of the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if there is any path from the root node down to any leaf node where the sum of the node values equals the target sum.

2. Step 2: Differentiate from other tree properties

   It is not about depth, total nodes, or sum of all nodes, but specifically about a path sum from root to leaf.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option B

4. Quick Check:

   Path sum means root-to-leaf sum = D [OK]

Hint: Focus on root-to-leaf paths, not entire tree sums [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not just root-to-leaf
• Ignoring leaf node condition

2. Which of the following TypeScript function signatures correctly represents a function to check path sum in a binary tree node defined as class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }?

easy

A. function hasPathSum(root: number, sum: TreeNode): boolean

B. function hasPathSum(root: TreeNode, sum: string): boolean

C. function hasPathSum(root: TreeNode | null, sum: number): boolean

D. function hasPathSum(root: TreeNode | null): number

Solution

1. Step 1: Check parameter types

   The root should be a TreeNode or null (empty tree), and sum should be a number representing the target sum.

2. Step 2: Check return type

   The function returns a boolean indicating if such a path exists.

3. Final Answer:

   function hasPathSum(root: TreeNode | null, sum: number): boolean -> Option C

4. Quick Check:

   Correct types and return boolean = B [OK]

Hint: Root can be null; sum is number; return boolean [OK]

Common Mistakes:

• Swapping parameter types
• Using wrong return type
• Missing null for root parameter

3. Given the following binary tree and target sum = 22, what will the function hasPathSum(root, 22) return?

    5
   / \
  4   8
 /   / \
11  13  4
/  \      
7    2     1

medium

A. null

B. false

C. SyntaxError

D. true

Solution

1. Step 1: Identify root-to-leaf paths and their sums

   Check paths: 5->4->11->7 = 27, 5->4->11->2 = 22, 5->8->13 = 26, 5->8->4->1 = 18.

2. Step 2: Check if any path sum equals 22

   Path 5->4->11->2 sums to 22, so function returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Path sum 22 exists = true [OK]

Hint: Sum each root-to-leaf path, check for target [OK]

Common Mistakes:

• Ignoring leaf node condition
• Calculating sum incorrectly
• Confusing partial paths with full root-to-leaf

4. Consider this TypeScript code snippet for checking path sum:

function hasPathSum(root: TreeNode | null, sum: number): boolean {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === sum;
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

What does the function return if the tree is empty (root = null) and sum is 0?

medium

A. Returns false for empty tree and sum 0

B. Causes infinite recursion

C. Throws runtime error due to null access

D. Returns true incorrectly for non-empty tree

Solution

1. Step 1: Analyze base case for empty tree

   When root is null, if (!root) returns false immediately.

2. Step 2: Confirm for sum = 0

   Empty tree has no root-to-leaf path regardless of target sum, so false is correct.

3. Final Answer:

   Returns false for empty tree and sum 0 -> Option A

4. Quick Check:

   Null root always returns false [OK]

Hint: Empty tree always returns false [OK]

Common Mistakes:

• Thinking empty tree with sum 0 should return true
• Expecting runtime error without null check
• Confusing empty tree with single-node tree

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which approach best solves this problem?

hard

A. Use DFS to track current path and sum, collect paths when sum matches at leaf

B. Use BFS and stop at first matching path

C. Use a queue to store sums only, ignoring paths

D. Return true or false immediately when sum matches any node

Solution

1. Step 1: Understand requirement to collect all matching paths

   We need to find all root-to-leaf paths whose sums equal the target, not just check existence.

2. Step 2: Choose traversal and tracking method

   DFS (depth-first search) allows tracking the current path and sum, and collecting paths when leaf and sum match.

3. Step 3: Evaluate other options

   BFS is less natural for path tracking; queues without paths lose information; returning boolean stops early.

4. Final Answer:

   Use DFS to track current path and sum, collect paths when sum matches at leaf -> Option A

5. Quick Check:

   DFS with path tracking = A [OK]

Hint: Track path and sum with DFS to collect all matching paths [OK]

Common Mistakes:

• Using BFS without path tracking
• Stopping at first match instead of collecting all
• Ignoring leaf node condition