DSA sheet · Trees · DFS pattern

Path Sum

This is the first root-to-leaf path problem in the sheet. The teacher uses it to teach three things: how to read the constraints for overflow, how to choose between DFS and BFS by thinking about best and worst cases, and a neat trick: instead of adding up a running sum, subtract each node from the target as you go down. She solves it with DFS first, then BFS. Path Sum II (next problem) builds directly on this one.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Path Sum with DFS
• Part B · Path Sum with BFS
• Part C · Revision page

Part 0 · Before starting

• Leaf: a node with no children at all (left is None and right is None).
• Root-to-leaf path: start at the root and keep going down, one child at a time, until you stop at a leaf. You may not stop halfway.
• Level: the root is on level 0, its children on level 1, and so on. A path takes exactly one node from each level it passes through.
• Height (h): the number of levels. Balanced tree with n nodes → about log₂ n levels. Skewed tree (a straight line) → n levels.
• Overflow: in Java/C++ an int holds values up to about 2.1 × 10⁹. A bigger result "wraps around" and becomes garbage. Python ints never overflow, but the teacher still checks for it, and so should you in interviews.

Part A · Path Sum with DFS

LeetCode 112

1The question in simple words

You get the root of a binary tree and a number targetSum. Return True if there is at least one root-to-leaf path whose node values add up to exactly targetSum. Otherwise return False.

            5
           / \
          4   8
         /   / \
       11   13  4
       / \       \
      7   2       1          targetSum = 22

This tree has 4 root-to-leaf paths (one per leaf):

One path works, so the answer is True. We only need to know whether such a path exists, not which one.

2What the constraints tell us

• Nodes: 0 to 5000 → the tree can be empty, so the root itself can be None.
• The teacher's rule about base cases:
  • DFS always needs a base case, even when the tree is never empty. The recursion keeps going down and will reach a None child at some point. Something has to stop it.
  • BFS only needs one if the tree can be empty. BFS puts the root in a queue at the start. If there's at least one node, the loop ends by itself when the queue empties. Here n can be 0, so BFS needs a check too.
• Values: −1000 to 1000 and we add them along a path → we should check for overflow. The teacher works out the biggest possible sum:
  • Skewed tree (all 5000 nodes in one line, so one path holds all of them), every value 1000: 5 × 10³ × 10³ = 5 × 10⁶.
  • Balanced tree: a path holds only one node per level. log₂ 5000 ≈ 12 to 13 levels → about 13 × 1000 ≈ 13,000.
  Both are far below the int limit (about 2 × 10⁹), so a normal int is safe. Only if the worst sum could pass about 10⁹ would we switch to long.
• Negative values are allowed. Remember this, because it matters for the base case below.

3Intuition: DFS or BFS?

Before writing code, the teacher asks: which traversal fits this problem better? She compares the best and worst cases.

• DFS walks one full path from root to leaf, then backs up and tries the next path. As soon as it reaches a leaf, it knows that path's total.
• BFS goes level by level. It fills the queue with level 1, then level 2, and so on. It can't finish any path until it reaches the leaf level.

Worst cases are equal, but DFS has a better best case. And the problem is literally about paths from top to bottom, which is how DFS moves. So she goes with DFS.

The mental picture

Think of targetSum as a budget you carry down the tree. At each node you spend that node's value. When you reach a leaf, you want to have spent the budget exactly.

4Building the logic from the example

What does each DFS call need?

• The node we are at, so we can move left or right.
• Some way to know how much of the sum we've collected so far.

Two ways to track the sum (the teacher shows both)

She uses Way 2 and walks it on the example. Start at 5 needing 22. We found 5, so below 5 we only need 17. At 4 we found 4, so below it we need 13. At 11 we found 11, so below it we need 2.

• Go to 7: we need 2 but got 7. 2 − 7 = −5, not 0. And 7 is a leaf, so this path is done and wrong. Go back.
• Back at 11, nothing has changed there: the recursion remembers that below 11 we needed 2. (Each call keeps its own copy of the number.)
• Go to 2: we need 2, and 2 − 2 = 0, at a leaf → valid path.

Rule 1: the base case, root is None → False

The teacher asks a tricky question first: if the node is None and targetSum is 0, should we return True? It's tempting: "nothing left to find, nothing here, so it matches."

No. A target of 0 is a perfectly normal target. Values can be negative, so a real path like 5 → −5 adds up to 0. But an empty spot isn't a path at all. No node, no path, so the answer is False, whatever the target is.

Rule 2: only judge the sum at a leaf

The question says root-to-leaf. We may only say "yes, this works" when we stand on a leaf. A leaf is a node where root.left is None and root.right is None.

Her first draft at a leaf was "return True if targetSum is 0". The dry run showed a problem with that. When the call for leaf 7 starts, the target it receives is 2. We haven't subtracted 7 yet, because the subtraction happens only when we pass the value down to the children. So at the leaf, the right check is "is the remaining target equal to this leaf's value?", i.e. targetSum == root.val.

Rule 3: not a leaf → ask the children, with a smaller target

The good path, if there is one, continues either through the left child or through the right child. So we ask both. What target do we send them? Not 22 again, because 5 is already part of every path below 5. We send targetSum − root.val = 17.

5Approach steps

1. If the node is None → return False.
2. If the node is a leaf → return whether the remaining target equals its value.
3. Otherwise subtract the node's value from the target, and ask the left child or the right child with the new target.

6Code (Python)

class Solution:
    def hasPathSum(self, root, targetSum):
        if root is None:                                   # Rule 1: no node, no path
            return False
        if root.left is None and root.right is None:       # Rule 2: leaf
            return targetSum == root.val
        remaining = targetSum - root.val                   # spend this node's value
        return (self.hasPathSum(root.left, remaining) or   # Rule 3: either side
                self.hasPathSum(root.right, remaining))

At the end of the video, the teacher leaves you a task: solve it with Way 1 (a running sum) too. Here it is. Only the bookkeeping changes.

class Solution:
    def hasPathSum(self, root, targetSum):
        return self.dfs(root, 0, targetSum)

    def dfs(self, node, s, targetSum):
        if node is None:
            return False
        s += node.val                                      # add instead of subtract
        if node.left is None and node.right is None:
            return s == targetSum                          # whole path collected
        return self.dfs(node.left, s, targetSum) or self.dfs(node.right, s, targetSum)

7Code line by line

8Dry run using the call stack

Each call is written as (node, target it received).

1. (5, 22): not None, not a leaf → remaining 17 → call left. (5,22) waits.
2. (4, 17): not a leaf (it has 11) → remaining 13 → call left. (4,17) waits.
3. (11, 13): not a leaf → remaining 2 → call left.
4. (7, 2): leaf! Is 2 == 7? No → False. This call leaves the stack.
5. Back in (11, 13): left said False, so or calls the right: (2, 2): leaf! Is 2 == 2? Yes → True. It leaves the stack.
6. (11, 13) gets False or True = True → returns to (4, 17) and leaves the stack.
7. (4, 17): left gave True, so the right call (None) is skipped → returns True.
8. (5, 22): left gave True → the whole right side (8, 13, 4, 1) is skipped → final answer True ✓

The teacher's point about space: (7, 2) left the stack before (2, 2) came in. At any moment the stack holds at most one call per level.

9Complexity & remember

• Time O(n): in the worst case (the good path is the last one, or there is none) we visit every node once.
• Space O(h): the stack holds one call per level of the current path. Balanced → O(log n). Skewed → O(n).

Part B · Path Sum with BFS

Same question, same rules, but we walk the tree level by level with a queue.

1The question & constraints

Same as Part A. One constraint matters more here: 0 nodes is allowed. So BFS needs a check at the top. If the root is None we must not put it in the queue and then read .left from it.

2Intuition: what does the queue need to hold?

In DFS, each call carried two things: the node and the target for that node. The call stack kept them together for us. A queue has no calls, so we must keep the pair together ourselves: each queue entry is (node, target for this node).

The teacher notes that Java needs a small Pair class for this and C++ has pair. In Python we just put a tuple in the queue: (node, target).

3Building the logic

• Pop a pair (node, target).
• Check this node first: if it's a leaf and target == node.val → return True right away.
• Otherwise push the children that exist, each with target − node.val. Unlike Same Tree's BFS, we don't push None here, because nothing is being compared in pairs.
• If the queue runs out and we never returned True → return False.

4Approach steps

1. If root is None → return False.
2. Queue starts with (root, targetSum).
3. While the queue isn't empty: pop (node, target).
4. Leaf and target == node.val → return True.
5. Push (node.left, target − node.val) if left exists, and the same for right.
6. After the loop → return False.

5Code (Python)

from collections import deque

class Solution:
    def hasPathSum(self, root, targetSum):
        if root is None:                          # 0 nodes is allowed
            return False
        queue = deque([(root, targetSum)])        # (node, target for this node)
        while queue:
            node, target = queue.popleft()
            if node.left is None and node.right is None:
                if target == node.val:            # good leaf: done
                    return True
            remaining = target - node.val
            if node.left:
                queue.append((node.left, remaining))
            if node.right:
                queue.append((node.right, remaining))
        return False

6Code line by line

7Dry run: watch the queue

Same tree, target 22. Each box is (node, target). Yellow = popped now.

Compare with DFS: DFS reached the answer after 5 calls on real nodes (5, 4, 11, 7, 2). BFS popped 8 pairs, including 8, 13 and the lower 4 from the right side. That's the "best case is better in DFS" point from Part A.

8Complexity & why BFS ran slower

• Time O(n): each node enters and leaves the queue once.
• Space O(n): the queue can hold a whole level, up to about n/2 nodes.

On LeetCode, the BFS version ran a bit slower. The teacher's reason: for every node we build a new pair and do queue operations, which cost more than plain recursive calls. Her verdict: for path problems, go with DFS. It's simpler and usually faster.

Part C · Revision page

root = TreeNode(5,
    TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
    TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1))))

s = Solution()
print(s.hasPathSum(root, 22))                      # True  (5-4-11-2)
print(s.hasPathSum(root, 26))                      # True  (5-8-13)
print(s.hasPathSum(root, 9))                       # False (5-4 stops at 4, not a leaf)
print(s.hasPathSum(None, 0))                       # False (empty tree)
print(s.hasPathSum(TreeNode(1, TreeNode(2)), 1))   # False (1 is not a leaf)

Based on this video: Path Sum | DFS & BFS