019 — Path Sum II¶

Source¶

Original source: Classic root-to-leaf path-collection exercise
Platform: LeetCode — https://leetcode.com/problems/path-sum-ii/
Topic: trees
Difficulty: Medium
Pattern: Path + backtracking
Basic idea inherited from: Path Sum + choose/explore/un-choose (../../06-recursion-and-backtracking/)

1. Problem in simple words¶

তোমাকে একটা binary tree আর একটা target সংখ্যা দেওয়া আছে। তোমার কাজ: এমন সব root-to-leaf path খুঁজে বের করা যেগুলোর node-value-র যোগফল ঠিক target-এর সমান। প্রতিটা path একটা list, আর সব path-এর একটা list-of-lists ফেরত দিতে হবে।

            5
           / \
          4   8        target = 22
         /   / \
        11  13  4      path 5→4→11→2 = 22 ✓
       /  \      \      path 5→8→4→1 = 18 ✗ (এই tree-তে অন্য সংখ্যায়)
      7    2      1

2. Which basic idea does this inherit from?¶

এটা Path Sum (#8)-এর উপর গড়ে ওঠে: সেখানে শুধু হ্যাঁ/না জানতে চাওয়া হতো "এমন কোনো path আছে কি?"। এখানে আমরা সব matching path জমাতে চাই, তাই যোগ হয় ../../06-recursion-and-backtracking/-এর choose / explore / un-choose শৃঙ্খলা — নামার পথে node-টা path-এ append করো, ফেরার পথে pop করো।

3. What is the hidden math or logic?¶

লুকানো logic দুই অংশ — carry-down state আর backtracking:

নামার পথে: path-এ node যোগ করো, remaining = target - node.val
leaf-এ: remaining == 0 হলে path-এর একটা copy সংরক্ষণ করো
ফেরার পথে: path থেকে node সরাও (un-choose)

মূল গণিত হলো decrease-and-conquer (remaining কমতে থাকে), আর মূল শৃঙ্খলা হলো backtracking — একই path list সব branch-এ পুনর্ব্যবহার করতে।

4. Which data structure is needed?¶

একটা list path (বর্তমান root-to-current chain ধরে রাখে, append/pop দিয়ে), recursion call stack (কোন path-এ আছি মনে রাখে), আর একটা result list (matching path-গুলোর copy জমায়)।

5. Why this data structure fits¶

একটা মাত্র path list সব branch-এ পুনর্ব্যবহার করা সবচেয়ে কম-খরচের — নামার সময় append, ফেরার সময় pop, তাই প্রতিটা মুহূর্তে path-এ ঠিক বর্তমান chain থাকে। কিন্তু leaf-এ match পেলে অবশ্যই path[:] (একটা copy) result-এ দিতে হবে, কারণ পরে pop হয়ে গেলে মূল list বদলে যাবে।

6. Real-life analogy¶

একটা গোলকধাঁধায় তুমি সূতো বিছিয়ে এগোচ্ছ — প্রতিটা মোড়ে সূতো বাড়ছে (choose), গন্তব্যে পৌঁছে যদি ঠিক হয় তবে পুরো রুটের একটা ছবি তুলে রাখছ (copy), আর ফিরে আসার সময় সেই অংশের সূতো গুটিয়ে নিচ্ছ (un-choose) যাতে পরের শাখা পরিষ্কার থেকে শুরু হয়। সূতোটাই তোমার path।

7. Visual explanation¶

path নামার পথে বাড়ে, leaf-এ copy নেওয়া হয়, ফেরার পথে গুটায়:

            5            path [5],        remaining 17
           / \
          4   8          path [5,4],      remaining 13
         /
        11               path [5,4,11],   remaining 2
       /  \
      7    2             path [5,4,11,2], remaining 0 ✓ → copy [5,4,11,2]
                         তারপর 2 pop, 11 pop... অন্য শাখায় যাও

8. Example input and output¶

Input : root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22
Output: [[5, 4, 11, 2]]

Input : root = [1,2,3], target = 3      -> Output: [[1, 2]]
Input : root = [1,2,3], target = 4      -> Output: [[1, 3]]
Edge  : root = [], target = 0           -> Output: []        (path নেই)
Edge  : root = [1,2], target = 1        -> Output: []        (1 leaf না)

9. Brute force thinking¶

প্রথম সরল চিন্তা: tree-র সব root-to-leaf path আলাদা করে বের করি (প্রতিটা পুরো list বানিয়ে), তারপর প্রতিটার যোগফল মেপে target-এর সমান হলে রাখি।

1) সব path বের করো: [5,4,11,7], [5,4,11,2], [5,8,13], [5,8,4,1]
2) প্রতিটার যোগ: 27, 22, 26, 18
3) target 22-এর সমানগুলো রাখো: [[5,4,11,2]]

10. Why brute force is slow¶

প্রতিটা path আলাদা করে নতুন করে বানালে অনেক path-এর shared উপরের অংশ (যেমন [5,4,11]) বারবার তৈরি হয় — extra memory আর কাজ নষ্ট। Backtracking একই path list পুনর্ব্যবহার করে: শুধু এক node append/pop করে, পুরো prefix প্রতিবার নতুন করে বানায় না। Match পেলেই কেবল একটা copy নেয়।

11. Key observation¶

মূল observation: একই path list সব শাখায় চালানো যায়, যদি নামার সময় append আর ফেরার সময় pop করা হয় (backtracking)। আর leaf-এ match পেলে অবশ্যই একটা copy (path[:]) সংরক্ষণ করতে হবে — সরাসরি path রাখলে পরে pop হয়ে সেটা নষ্ট হয়ে যাবে।

12. Optimized intuition¶

এটা path + backtracking: DFS-এ নামার সময় path.append(node.val) আর remaining -= node.val; leaf-এ remaining == 0 হলে result.append(path[:]); দুই child-এ recurse করার পর path.pop() (un-choose)। প্রতিটা node একবার দেখা হয়; matching path copy করার খরচ আলাদা, কিন্তু সেটা অনিবার্য (output-এর আকার)।

13. Thinking tweak¶

মোচড়: "প্রতিটা path আলাদা করে বানাব" ভাবা বন্ধ করো। বরং ভাবো "একটাই path list রাখব, এগোলে বাড়াব, ফিরলে কমাব।" আর সবচেয়ে গুরুত্বপূর্ণ: match পেলে copy রাখো — কারণ মূল list-টা পরে বদলে যাবে। choose → explore → un-choose ছন্দটাই মূল।

14. Step-by-step dry run¶

Input ছোট tree [1,2,3], target = 3:

dfs(1, rem=3, path=[]): append 1 → path [1], rem = 2। 1 leaf না।
dfs(2, rem=2, path=[1]): append 2 → path [1,2], rem = 0। 2 leaf, rem==0 → copy [1, 2] সংরক্ষণ। pop → path [1]।
dfs(3, rem=2, path=[1]): append 3 → path [1,3], rem = -1। 3 leaf, rem ≠ 0 → কিছু না। pop → path [1]।
pop 1 → path []। result = [[1, 2]]।

15. Python solution¶

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values):
    """level-order list (None = missing child) থেকে tree বানায়।"""
    if not values:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


def path_sum(root, target):
    result, path = [], []

    def dfs(node, remaining):
        if node is None:                 # খালি subtree: কোনো path নেই
            return
        path.append(node.val)            # choose
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            result.append(path[:])       # leaf-এ ঠিক যোগ → copy সংরক্ষণ
        else:
            dfs(node.left, remaining)    # explore বাঁ দিক
            dfs(node.right, remaining)   # explore ডান দিক
        path.pop()                       # un-choose (backtrack)

    dfs(root, target)
    return result


# ---- tests ----
big = build_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1])
assert path_sum(big, 22) == [[5, 4, 11, 2]]
assert path_sum(build_tree([1, 2, 3]), 3) == [[1, 2]]
assert path_sum(build_tree([1, 2, 3]), 4) == [[1, 3]]
assert path_sum(build_tree([]), 0) == []
assert path_sum(build_tree([1, 2]), 1) == []     # 1 leaf না, তাই match না
print("সব test pass!")

16. Line-by-line code explanation¶

result, path = [], [] — matching path-এর copy জমাবে result; বর্তমান chain রাখবে path।
if node is None: return — খালি subtree, কিছু করার নেই।
path.append(node.val) — choose: এই node বর্তমান path-এ যোগ করো।
remaining -= node.val — target থেকে এই value বাদ; কত আর বাকি।
if ... leaf and remaining == 0: result.append(path[:]) — leaf-এ ঠিক যোগ মিললে path-এর একটা copy রাখো (সরাসরি path না, কারণ পরে বদলাবে)।
dfs(node.left/right, remaining) — explore: দুই দিকে নামো।
path.pop() — un-choose: ফেরার পথে এই node সরিয়ে দাও, যাতে পরের শাখা পরিষ্কার থেকে শুরু হয়।

17. Output walkthrough¶

build_tree([5,4,8,11,None,13,4,7,2,None,None,None,1]) ওই ছবির tree বানায়; path_sum(big, 22) [[5, 4, 11, 2]] ফেরত দেয় — assert pass। [1,2,3] target 3 দেয় [[1, 2]], target 4 দেয় [[1, 3]], খালি tree দেয় [], আর [1,2] target 1 দেয় [] (1 leaf না) — সব pass। শেষে print: সব test pass!।

18. Time complexity¶

O(n²) সবচেয়ে খারাপ ক্ষেত্রে — প্রতিটা node একবার visit (O(n)), কিন্তু matching path copy করতে প্রতিটা O(n) লম্বা হতে পারে আর O(n) সংখ্যক path থাকতে পারে। শুধু traversal O(n); copy-র খরচ output-এর আকারের সমান।

19. Space complexity¶

O(h) auxiliary — recursion call stack আর path list দুটোই height h-এর সমান গভীর/লম্বা হয়। (output result আলাদা, তার আকার matching path-এর মোট দৈর্ঘ্যের সমান।)

20. Common mistakes¶

match পেলে result.append(path) (copy ছাড়া) লেখা — পরে pop হয়ে গেলে সব সংরক্ষিত reference খালি/ভুল হয়ে যায়; path[:] লাগবে।
path.pop() ভুলে যাওয়া — তখন path পরের শাখায়ও পুরোনো node বয়ে নিয়ে যায়, সব উত্তর ভুল।
leaf check ভুল করা: শুধু remaining == 0 দেখা যথেষ্ট না; node-টা সত্যিই leaf (দুই child None) হতে হবে, কারণ এটা root-to-leaf path।

21. Which basic problem this inherits from¶

ভিত্তি: Path Sum (#8)-এর carry-down remaining আর ../../06-recursion-and-backtracking/-এর choose/explore/un-choose; traversal-patterns.md-র Pattern A (path problems)-ও এটাই। হ্যাঁ/না থেকে "সব path জমাও"-তে যেতে শুধু backtracking যোগ হয়।

22. Similar harder problems¶

Path Sum III (যেকোনো node থেকে যেকোনো node, prefix-sum সহ) — https://leetcode.com/problems/path-sum-iii/
Binary Tree Paths (সব root-to-leaf path, sum-শর্ত ছাড়া) — https://leetcode.com/problems/binary-tree-paths/
Sum Root to Leaf Numbers (প্রতিটা path-কে সংখ্যা ধরে যোগ) — https://leetcode.com/problems/sum-root-to-leaf-numbers/

23. Pattern learned¶

Path collection with backtracking: একটাই path list রাখো; নামার সময় append (choose), শর্ত মিললে leaf-এ একটা copy সংরক্ষণ করো, ফেরার সময় pop (un-choose)। সব root-to-leaf path-জাতীয় problem-এর কঙ্কাল এটাই — copy নেওয়া আর pop করা ভুললেই bug।

24. Final summary¶

ভবিষ্যতের আমাকে: "সব matching path = একটা path list-এ append/pop, leaf-এ match পেলে path[:] copy রাখো।" choose → explore → un-choose ছন্দ আর copy-নেওয়া — এই দুটোই মূল। 'সব path / সব combination জমাও' টাইপ tree problem দেখলেই এই backtracking চালটা মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।