Problem link ও উৎস
- **Original source:** Classic root-to-leaf path-collection exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Path + backtracking
- **Basic idea inherited from:** Path Sum + choose/explore/un-choose ([../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree আর একটা target সংখ্যা দেওয়া আছে। তোমার কাজ: এমন **সব root-to-leaf path** খুঁজে বের করা যেগুলোর node-value-র যোগফল ঠিক target-এর সমান। প্রতিটা path একটা list, আর সব path-এর একটা list-of-lists ফেরত দিতে হবে।
```text
5
/ \
4 8 target = 22
/ / \
11 13 4 path 5→4→11→2 = 22 ✓
/ \ \ path 5→8→4→1 = 18 ✗ (এই tree-তে অন্য সংখ্যায়)
7 2 1
```
### Input ও output {#8-example-input-and-output}
```text
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 না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা গোলকধাঁধায় তুমি সূতো বিছিয়ে এগোচ্ছ — প্রতিটা মোড়ে সূতো বাড়ছে (choose), গন্তব্যে পৌঁছে যদি ঠিক হয় তবে পুরো রুটের একটা ছবি তুলে রাখছ (copy), আর ফিরে আসার সময় সেই অংশের সূতো গুটিয়ে নিচ্ছ (un-choose) যাতে পরের শাখা পরিষ্কার থেকে শুরু হয়। সূতোটাই তোমার `path`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Path Sum** (#8)-এর উপর গড়ে ওঠে: সেখানে শুধু হ্যাঁ/না জানতে চাওয়া হতো "এমন কোনো path আছে কি?"। এখানে আমরা **সব matching path জমাতে** চাই, তাই যোগ হয় [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md)-এর **choose / explore / un-choose** শৃঙ্খলা — নামার পথে node-টা path-এ append করো, ফেরার পথে pop করো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই অংশ — carry-down state আর backtracking:
```text
নামার পথে: 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 বদলে যাবে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: tree-র সব root-to-leaf path আলাদা করে বের করি (প্রতিটা পুরো list বানিয়ে), তারপর প্রতিটার যোগফল মেপে target-এর সমান হলে রাখি।
```text
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 ছন্দটাই মূল।
### ছবিতে বোঝা {#7-visual-explanation}
Input tree-এর সব node নিচে আছে। `target=22`; root থেকে leaf পর্যন্ত যোগফল 22 হলেই শুধু path নেব।
```mermaid
flowchart TD
n5["5"] --> n4["4"]
n5 --> n8["8"]
n4 --> n11["11"]
n11 --> n7["7"]
n11 --> n2["2"]
n8 --> n13["13"]
n8 --> r4["4"]
r4 --> n1["1"]
```
| DFS-এ শেষ হওয়া leaf-path | Sum | ফল |
| --- | --- | --- |
| [5,4,11,7] | 27 | বাদ; 7 pop করলে path [5,4,11] |
| [5,4,11,2] | 22 | Copy রাখুন; 2 pop করলে [5,4,11] |
| [5,8,13] | 26 | বাদ; 13 pop করলে [5,8] |
| [5,8,4,1] | 18 | বাদ; 1 pop করলে [5,8,4] |
বাঁ subtree শেষ হলে 11 ও 4 pop করে path আবার [5] হয়; তারপর 8-এ নামি। ডান subtree শেষ হলে 4, 8, 5 ফেরার সময় pop হয়। শেষে working path খালি, কিন্তু copy করা result `[[5,4,11,2]]` অক্ষত থাকে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input ছোট tree `[1,2,3]`, `target = 3`:
1. `dfs(1, rem=3, path=[])`: append 1 → path `[1]`, rem = 2। 1 leaf না।
2. `dfs(2, rem=2, path=[1])`: append 2 → path `[1,2]`, rem = 0। 2 leaf, rem==0 → copy `[1, 2]` সংরক্ষণ। pop → path `[1]`।
3. `dfs(3, rem=2, path=[1])`: append 3 → path `[1,3]`, rem = -1। 3 leaf, rem ≠ 0 → কিছু না। pop → path `[1]`।
4. pop 1 → path `[]`। result = `[[1, 2]]`।
## কোড ও ব্যাখ্যা {#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 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 সরিয়ে দাও, যাতে পরের শাখা পরিষ্কার থেকে শুরু হয়।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Path Sum (#8)-এর carry-down remaining আর [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md)-এর choose/explore/un-choose; traversal-patterns.md-র Pattern A (path problems)-ও এটাই। হ্যাঁ/না থেকে "সব path জমাও"-তে যেতে শুধু backtracking যোগ হয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Path Sum III (যেকোনো node থেকে যেকোনো node, prefix-sum সহ) —