Problem link ও উৎস
- **Original source:** Classic root-to-leaf path exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Easy
- **Pattern:** Path (carry state down)
- **Basic idea inherited from:** Remaining target-এর উপর decrease-and-conquer — নামার পথে target থেকে value বিয়োগ করতে করতে যাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root আর একটা সংখ্যা `targetSum` দেওয়া আছে। তোমার কাজ: বলো এমন কোনো **root-to-leaf path** আছে কিনা যার সব node-এর value যোগ করলে ঠিক `targetSum` হয়। (Leaf = যার কোনো child নেই।)
```text
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1 targetSum = 22 → path 5→4→11→2 = 22 ✓ → True
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
হাতে একটা নির্দিষ্ট টাকা নিয়ে কেনাকাটায় বেরোনোর কথা ভাবো। প্রতিটা দোকানে (node) কিছু খরচ করো — পকেটে বাকি টাকা কমে। রাস্তার শেষ মোড়ে (leaf) পৌঁছে দেখো: বাকি টাকা ঠিক এই শেষ জিনিসটার দামের সমান কিনা — মিললে এই পথে পুরো বাজেট খরচ হয়েছে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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/](../../06-recursion-and-backtracking/README.md)-এ একটা সমস্যা ছোট করে নিচে পাঠানো হয়। leaf-এ পৌঁছে দেখি অবশিষ্ট target ঠিক leaf-এর value-র সমান কিনা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো target-কে নামতে নামতে কমানো:
```text
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 একে অপরের হিসাব নষ্ট করে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: tree-র **সব root-to-leaf path** আলাদা করে বের করি, প্রতিটার যোগফল হিসাব করি, তারপর দেখি কোনোটা `targetSum`-এর সমান কিনা।
```text
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 লাগে না।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা node-এ ছোট সংখ্যাটা সেই মুহূর্তে "বাকি কত দরকার" (remaining), নিজের value বিয়োগের পর:
```text
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)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `root = [1,2,3]` (root 1, left 2, right 3), `targetSum = 5`:
1. `has(1, 5)`: leaf না; বিয়োগ 1 → বাকি 4 দুই child-এ পাঠাও।
2. `has(2, 4)`: 2 leaf; বাকি 4 == value 2? না → False।
3. `has(3, 4)`: 3 leaf; বাকি 4 == value 3? না → False।
4. `False or False` → **False** (কোনো path 5 দেয় না: 1+2=3, 1+3=4)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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, আর সেটা পেলেই থামে।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 দেখতে হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md)-র 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) —