008 — Path Sum¶

Source¶

Original source: Classic root-to-leaf path exercise
Platform: LeetCode — https://leetcode.com/problems/path-sum/
Topic: trees
Difficulty: Easy
Pattern: Path (carry state down)
Basic idea inherited from: Remaining target-এর উপর decrease-and-conquer — নামার পথে target থেকে value বিয়োগ করতে করতে যাও

1. Problem in simple words¶

তোমাকে একটা binary tree-র root আর একটা সংখ্যা targetSum দেওয়া আছে। তোমার কাজ: বলো এমন কোনো root-to-leaf path আছে কিনা যার সব node-এর value যোগ করলে ঠিক targetSum হয়। (Leaf = যার কোনো child নেই।)

        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1     targetSum = 22 → path 5→4→11→2 = 22 ✓ → True

2. Which basic idea does this inherit from?¶

এটা decrease-and-conquer-এর tree-রূপ (traversal-patterns.md-র Pattern A: path problems)। প্রতিটা node-এ আমরা target থেকে নিজের value বিয়োগ করে ছোট হয়ে যাওয়া target নিচে পাঠাই — ঠিক যেমন ../../06-recursion-and-backtracking/-এ একটা সমস্যা ছোট করে নিচে পাঠানো হয়। leaf-এ পৌঁছে দেখি অবশিষ্ট target ঠিক leaf-এর value-র সমান কিনা।

3. What is the hidden math or logic?¶

লুকানো logic হলো target-কে নামতে নামতে কমানো:

has_path(empty, target)      = False
has_path(leaf,  target)      = (target == leaf.val)
has_path(node,  target)      = has_path(node.left,  target - node.val)
                            or has_path(node.right, target - node.val)

মানে "বাকি কত যোগ করতে হবে" সেই state নিচে বয়ে নিয়ে যাওয়া। leaf-এ এসে দেখা: এই leaf-টা নিলে কি ঠিক শূন্যে নামে? or থাকায় যেকোনো একটা path মিললেই True।

4. Which data structure is needed?¶

কোনো extra data structure লাগে না। শুধু recursion call stack — প্রতিটা call একটা সংখ্যা (অবশিষ্ট target) বহন করে। state-টা argument হিসেবেই নিচে যায়, আলাদা stack/list লাগে না।

5. Why this data structure fits¶

Tree self-similar (concept.md দেখো), আর path-প্রশ্নের state (remaining sum) একটা সাধারণ সংখ্যা — function argument-এ নিচে পাঠানোই সবচেয়ে স্বাভাবিক। call stack প্রতিটা path-এ নিজের আলাদা remaining value মনে রাখে, তাই দুই ভাই-subtree একে অপরের হিসাব নষ্ট করে না।

6. Real-life analogy¶

হাতে একটা নির্দিষ্ট টাকা নিয়ে কেনাকাটায় বেরোনোর কথা ভাবো। প্রতিটা দোকানে (node) কিছু খরচ করো — পকেটে বাকি টাকা কমে। রাস্তার শেষ মোড়ে (leaf) পৌঁছে দেখো: বাকি টাকা ঠিক এই শেষ জিনিসটার দামের সমান কিনা — মিললে এই পথে পুরো বাজেট খরচ হয়েছে।

7. Visual explanation¶

প্রতিটা node-এ ছোট সংখ্যাটা সেই মুহূর্তে "বাকি কত দরকার" (remaining), নিজের value বিয়োগের পর:

        5   need 22  → বিয়োগ 5, নিচে পাঠাও 17
       / \
need  4   8  need 17
 17  /
    11  need 13 → বিয়োগ 11, নিচে পাঠাও 2
   /  \
  7    2  need 2 → leaf, value 2 == 2 ✓ → True
 need
  6 (≠7)

8. Example input and output¶

Input : root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: True                     (path 5→4→11→2)

Input : root = [1,2,3], targetSum = 5    -> Output: False  (paths দেয় 3, 4)
Input : root = [], targetSum = 0         -> Output: False  (খালি tree-তে কোনো path নেই)
Input : root = [1], targetSum = 1        -> Output: True   (একক node, নিজেই leaf)

9. Brute force thinking¶

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

1) সব path বের করো: [5,4,11,7], [5,4,11,2], [5,8,13], [5,8,4,1]
2) যোগফল: 27, 22, 26, 18
3) 22 আছে? হ্যাঁ → True

10. Why brute force is slow¶

সব path আলাদা list-এ জমালে অনেক path-এর shared উপরের অংশ (যেমন 5→4→11) বারবার লেখা হয় — extra memory আর কাজ নষ্ট। আসলে পুরো path জমানোর দরকার নেই; প্রতিটা node-এ শুধু একটা সংখ্যা — "বাকি কত" — নিচে নিলেই চলে। তাছাড়া match পেলে or সঙ্গে সঙ্গে থেমে যায়, সব path বের করার দরকারই নেই।

11. Key observation¶

মূল observation: পুরো path-এর যোগফল রাখার দরকার নেই — শুধু "বাকি কত দরকার" রাখলেই চলে। target থেকে নামতে নামতে value বিয়োগ করো, তাহলে leaf-এ এসে প্রশ্নটা সহজ হয়ে যায়: "এই leaf-এর value কি ঠিক অবশিষ্ট target-এর সমান?"

12. Optimized intuition¶

প্রতিটা node-এ target থেকে নিজের value বিয়োগ করে নতুন target দুই child-এ পাঠাও। None-এ False ফেরাও। leaf-এ (দুই child None) দেখো অবশিষ্ট target == এই node-এর value কিনা। দুই child-এর ফলাফল or করো — একটা path মিললেই যথেষ্ট। পুরো tree একবার ঘোরা (worst case), match পেলে আগেই থামে।

13. Thinking tweak¶

মোচড়: "path-এর যোগফল উপরে জমা করব" ভাবা বন্ধ করো। বরং state-টা নিচে বহন করো — target থেকে বিয়োগ করতে করতে যাও। এই দিক-পাল্টানো (carry-down) leaf-এর শর্তটাকে এক লাইনে করে দেয়: "বাকি target == leaf value?" — আর কোনো accumulator লাগে না।

14. Step-by-step dry run¶

Input root = [1,2,3] (root 1, left 2, right 3), targetSum = 5:

has(1, 5): leaf না; বিয়োগ 1 → বাকি 4 দুই child-এ পাঠাও।
has(2, 4): 2 leaf; বাকি 4 == value 2? না → False।
has(3, 4): 3 leaf; বাকি 4 == value 3? না → False।
False or False → False (কোনো path 5 দেয় না: 1+2=3, 1+3=4)।

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 has_path_sum(node, target):
    if node is None:                         # খালি subtree: কোনো path নেই
        return False
    if node.left is None and node.right is None:   # leaf-এ পৌঁছালাম:
        return target == node.val            # বাকি target কি ঠিক এই value?
    rest = target - node.val                 # নিজের value বিয়োগ করে
    return (has_path_sum(node.left, rest)     # বাঁ-পথে বাকিটা খোঁজো
            or has_path_sum(node.right, rest))  # বা ডান-পথে — একটা মিললেই হলো


# ---- tests ----
big = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1]
assert has_path_sum(build_tree(big), 22) is True            # 5→4→11→2
assert has_path_sum(build_tree([1, 2, 3]), 5) is False      # paths দেয় 3, 4
assert has_path_sum(build_tree([]), 0) is False             # খালি tree
assert has_path_sum(build_tree([1]), 1) is True             # একক node = leaf
assert has_path_sum(build_tree([1, 2]), 1) is False         # leaf 2-এ থামতে হয়, root-এ না
print("সব test pass!")

16. Line-by-line code explanation¶

if node is None: return False — খালি subtree-তে কোনো path থাকতে পারে না।
if node.left is None and node.right is None: return target == node.val — leaf-এর শর্ত: অবশিষ্ট target ঠিক এই leaf-এর value হলেই path মিলেছে।
rest = target - node.val — মূল চাল: নিজের value বিয়োগ করে "বাকি কত" বের করা।
return has_path_sum(node.left, rest) or has_path_sum(node.right, rest) — দুই দিকে বাকি target পাঠাও; or যেকোনো একটা মিললেই True, আর সেটা পেলেই থামে।

17. Output walkthrough¶

বড় tree-তে 5→4→11→2 path-এর যোগ 22, তাই True। [1,2,3] target 5 → False (dry run-এর সাথে মেলে)। খালি tree → False; একক node [1] target 1 → True (নিজেই leaf); [1,2] target 1 → False (leaf 2-এ থামতে হয়, root 1-এ থামা যায় না, কারণ root leaf নয়)। সব assert pass, শেষে print: সব test pass!।

18. Time complexity¶

O(n) — worst case-এ প্রতিটা node একবার করে visit হয়। match আগে পাওয়া গেলে আরও কম (short-circuit)।

19. Space complexity¶

O(h) — recursion call stack tree-র height h সমান গভীর হয়। balanced-এ O(log n), chain-এ O(n)। (concept.md-র table দেখো।) state শুধু একটা সংখ্যা, তাই বাড়তি কিছু লাগে না।

20. Common mistakes¶

leaf-এর শর্ত ভুলে গিয়ে যেকোনো node-এ target == node.val চেক করা → root-to-leaf না হওয়া আংশিক path-ও ভুলভাবে True দেয় (যেমন [1,2] target 1)।
খালি tree-তে target 0-কে True ভাবা → কোনো path-ই নেই, তাই False।
নেগেটিভ value থাকলে "value কমলে আর match হবে না" ধরে আগেই থেমে যাওয়া — সব path দেখতে হয়।

21. Which basic problem this inherits from¶

ভিত্তি: ../../06-recursion-and-backtracking/-র decrease-and-conquer আর traversal-patterns.md-র Pattern A (path, state carry down)। "নিচে state পাঠাও, leaf-এ যাচাই করো" — এই কঙ্কালটাই path-জাতীয় সব problem-এর শুরু।

22. Similar harder problems¶

Path Sum II (শুধু আছে কিনা না, সব মিল-পথ list করো — choose/explore/un-choose) — https://leetcode.com/problems/path-sum-ii/ (এই tracker-এর #19)
Path Sum III (path যেকোনো node থেকে শুরু/শেষ হতে পারে) — https://leetcode.com/problems/path-sum-iii/
Sum Root to Leaf Numbers (প্রতিটা path একটা সংখ্যা গড়ে, সব যোগ করো) — https://leetcode.com/problems/sum-root-to-leaf-numbers/

23. Pattern learned¶

Carry-state-down path: target-এর মতো state নামার পথে argument হিসেবে বইয়ে নাও (এখানে বিয়োগ করতে করতে), আর সিদ্ধান্ত নাও leaf-এ। or দিয়ে "যেকোনো path?" প্রশ্ন short-circuit-সহ মেলে।

24. Final summary¶

ভবিষ্যতের আমাকে: "Path Sum = target থেকে নামতে নামতে value বিয়োগ করো; leaf-এ দেখো বাকি target == leaf value কিনা।" "root-to-leaf path", "path sum" শব্দ শুনলেই state-carry-down মনে পড়বে। মূল চাবি: যোগফল উপরে জমিও না, বাকিটা নিচে বহন করো।

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