Problem link ও উৎস
- **Original source:** Classic "best path anywhere in the tree" exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Hard
- **Pattern:** Diameter idea + values
- **Basic idea inherited from:** Diameter (#18), negative-pruning সহ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree দেওয়া আছে যার node-গুলোতে সংখ্যা (ঋণাত্মকও হতে পারে) আছে। একটা **path** মানে node-এর এমন একটা ক্রম যেখানে পরপর দুটো node edge দিয়ে যুক্ত, কোনো node দু'বার নয়, আর path-এ অন্তত একটা node থাকতেই হবে। তোমার কাজ: এমন path খুঁজে বের করা যার node-value-র যোগফল **সর্বোচ্চ**, আর সেই যোগফলটা ফেরত দেওয়া।
মূল মোচড়: path-কে root দিয়ে যেতে হবে না — সে tree-র যেকোনো জায়গায় শুরু ও শেষ হতে পারে, এমনকি একটা subtree-র ভেতরে বাঁ-পাশ থেকে উপরে উঠে ডান-পাশে নেমে যেতে পারে (একটা "∧" আকার)।
```text
-10
/ \
9 20 সেরা path: 15 → 20 → 7 = 42
/ \
15 7 (root -10 এড়িয়ে গেলেই ভালো)
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [1,2,3]
Output: 6 (2 → 1 → 3 = 6, পুরো ∧)
Input : root = [-10,9,20,null,null,15,7]
Output: 42 (15 → 20 → 7)
Edge : root = [-3] -> Output: -3 (একটামাত্র node, ঋণাত্মক হলেও নিতেই হবে)
Edge : root = [2,-1] -> Output: 2 (-1 বাদ, শুধু 2)
Edge : root = [-2,-1] -> Output: -1 (কম খারাপটা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো প্রতিটা শহর (node) একটা লাভ-বা-লোকসানের অঙ্ক দেয়, আর রাস্তা (edge) দিয়ে শহরগুলো জোড়া। তুমি সবচেয়ে লাভজনক একটানা রুট খুঁজছ। প্রতিটা মোড়ে দুই দিক থেকে আসা লাভ যোগ করে দেখো এই মোড়কে শীর্ষ ধরে কত লাভ হয় (∧ রুট)। কিন্তু এই মোড় ছেড়ে আরও উপরে গেলে তো একটাই দিক ধরে যেতে পারবে — তাই উপরে শুধু বেশি-লাভের দিকটা নাও। আর কোনো দিক লোকসানি হলে সেদিকে যেও-ই না (০ ধরো)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Diameter of Binary Tree** (#18)-এর সরাসরি জ্ঞাতি। Diameter-এ প্রতিটা node-এ তুমি দুই দিকের **height** যোগ করে সবচেয়ে লম্বা পথ পাশের একটা variable-এ রাখতে। এখানে height-এর জায়গায় **best downward path-sum** বসাও, আর "edge গোনা"-র জায়গায় "value যোগ করা"। নতুন যা যোগ হয়: ঋণাত্মক branch থাকলে সেটা **বাদ** (০ ধরা) — কারণ লোকসানি দিক নেওয়ার চেয়ে না নেওয়া ভালো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic-এ দুটো আলাদা মান আছে — একটা return করি, একটা পাশে track করি:
```text
gain(node):
node None হলে → 0
left = max(gain(node.left), 0) # ঋণাত্মক হলে বাদ
right = max(gain(node.right), 0) # ঋণাত্মক হলে বাদ
best = max(best, node.val + left + right) # এই node-এ চূড়া (∧) বানাও
return node.val + max(left, right) # উপরে শুধু একটা দিক নেওয়া যায়
```
মূল বুদ্ধি: parent-এর কাছে একটা path তো **একটা দিক দিয়েই** উঠতে পারে (`max(left, right)`), কিন্তু এই node-কে চূড়া ধরে একটা path **দুই দিকই** ব্যবহার করতে পারে — সেই দুই-দিক যোগফলই global উত্তরের প্রার্থী।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — **recursion (postorder)** আর একটা **side-channel variable** `best` (এখন পর্যন্ত পাওয়া সর্বোচ্চ path-sum)। tree নিজেই data structure; call stack নামার পথ মনে রাখে। `best`-কে nonlocal/list/attribute দিয়ে সব call-এ ভাগ করতে হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা node-এ আমাদের দুটো ভিন্ন জিনিস লাগে: (১) উপরে কী return করব (single-arm gain), আর (২) এখানে সেরা ∧-path কত (global update)। একটা **postorder recursion** ঠিক এই দুটো একসাথে দিতে পারে — child শেষ হলেই দুই arm পাওয়া যায়। আর global সর্বোচ্চটা যেহেতু যেকোনো node-এ ঘটতে পারে, একটা **side variable** সব node-এর প্রার্থীর মধ্যে সবচেয়ে বড়টা ধরে রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: tree-র **প্রতি জোড়া node**-কে এক path-এর দুই প্রান্ত ধরো, তাদের মাঝের পথের যোগফল বের করো, সবগুলোর সর্বোচ্চটা নাও।
```text
1) সব (u, v) জোড়ার জন্য:
2) u থেকে v পর্যন্ত একমাত্র path খোঁজো
3) সেই path-এর value যোগ করো
4) সব যোগফলের max নাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
জোড়ার সংখ্যা O(n²), আর প্রতি জোড়ার path বের করতে আরও O(n) পর্যন্ত — সব মিলিয়ে **O(n³)** (বা সাবধানে করলে O(n²))। বিশাল অপচয়, কারণ আলাদা আলাদা path-এর অনেক অংশ shared। আসল চাল: প্রতিটা node-কে path-এর **সর্বোচ্চ বিন্দু (চূড়া)** ধরে ভাবা — তখন প্রতিটা সম্ভাব্য সেরা path ঠিক একবার, একটা মাত্র postorder pass-এ দেখা হয়ে যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **যেকোনো path-এর একটা সর্বোচ্চ node থাকে** (যেখান থেকে দুই দিকে নামে, বা একদিকে)। সেই চূড়া-node-এ দাঁড়িয়ে উত্তর = `node.val + left_gain + right_gain`। কিন্তু এই node যখন তার parent-কে gain ফেরত দেবে, তখন **একটাই arm** দিতে পারে (`node.val + max(left, right)`) — কারণ একটা path parent-এ ঢুকে আবার এই node-এ ফিরে দুই arm নিতে পারে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা postorder `gain(node)` লেখো যা **এই node থেকে নিচে নামা সর্বোচ্চ single-arm path-sum** ফেরত দেয়। ভেতরে: দুই child-এর gain নাও, প্রত্যেকটা `max(…, 0)` দিয়ে ছেঁটে নাও (ঋণাত্মক branch বাদ)। তারপর `best`-কে `node.val + left + right` দিয়ে update করো (এই node চূড়া)। শেষে `node.val + max(left, right)` return করো। পুরো tree একবার ঘোরা → O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** দুটো প্রশ্ন কখনো মিলিয়ে ফেলো না — "উপরে কী দেব" (one arm) আর "এখানে সেরা কত" (two arms, global)। return করো এক arm, কিন্তু update করো দুই arm দিয়ে। আর দ্বিতীয় মোচড়: ঋণাত্মক gain মানে সেই দিক **এড়িয়ে যাও** — `max(gain, 0)`। এই দুটো বুঝলে Hard problem-টা Diameter-এর মতোই সহজ হয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা node দুই arm-এর gain (ঋণাত্মক হলে ০) নিয়ে ∧-চূড়া বানায়; `best` সব চূড়ার সর্বোচ্চ:
```text
-10 চূড়া এখানে: -10 + 15 + 0 = 5 (left=15, right বাদ)
/ \
9 20 চূড়া: 20 + 15 + 7 = 42 ← best!
/ \
15 7 leaf: gain 15, gain 7
20 উপরে দেয়: 20 + max(15,7) = 35
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`root = [-10, 9, 20, null, null, 15, 7]`, `best = -inf` দিয়ে শুরু:
1. `gain(9)`: leaf → left=right=0, `best = max(-inf, 9) = 9`, return 9।
2. `gain(15)`: leaf → `best = max(9, 15) = 15`, return 15।
3. `gain(7)`: leaf → `best = max(15, 7) = 15`, return 7।
4. `gain(20)`: left=15, right=7 → `best = max(15, 20+15+7) = 42`, return `20 + max(15,7) = 35`।
5. `gain(-10)`: left = max(9,0)=9, right = max(35,0)=35 → `best = max(42, -10+9+35=34) = 42`, return `-10 + 35 = 25`।
6. উত্তর = `best` = **42**।
## কোড ও ব্যাখ্যা {#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 max_path_sum(root):
best = float("-inf")
def gain(node):
nonlocal best
if node is None: # খালি subtree কোনো gain দেয় না
return 0
left = max(gain(node.left), 0) # ঋণাত্মক arm বাদ
right = max(gain(node.right), 0) # ঋণাত্মক arm বাদ
best = max(best, node.val + left + right) # এই node চূড়া (∧)
return node.val + max(left, right) # উপরে শুধু এক arm যায়
gain(root)
return best
# ---- tests ----
assert max_path_sum(build_tree([1, 2, 3])) == 6
assert max_path_sum(build_tree([-10, 9, 20, None, None, 15, 7])) == 42
assert max_path_sum(build_tree([-3])) == -3 # একক ঋণাত্মক node
assert max_path_sum(build_tree([2, -1])) == 2 # -1 arm বাদ
assert max_path_sum(build_tree([-2, -1])) == -1 # কম খারাপটা
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `best = float("-inf")` — global সর্বোচ্চ; `-inf` দিয়ে শুরু যাতে একটামাত্র ঋণাত্মক node-ও সঠিকভাবে নেওয়া হয়।
- `if node is None: return 0` — খালি subtree gain ০; এটাই "ঋণাত্মক বাদ"-এর neutral মান।
- `left = max(gain(node.left), 0)` — বাঁ arm-এর gain; ঋণাত্মক হলে ০ ধরে সেই দিক এড়িয়ে যাই।
- `right = max(gain(node.right), 0)` — একই, ডান arm-এর জন্য।
- `best = max(best, node.val + left + right)` — এই node-কে চূড়া ধরে দুই arm যোগ করা ∧-path; global update।
- `return node.val + max(left, right)` — parent-কে শুধু **এক** arm দেওয়া যায়, তাই বড় arm-টা বেছে নিয়ে নিজের value-সহ ফেরত।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,3]` দেয় 6 (পুরো ∧: 2→1→3) — assert pass। `[-10,9,20,null,null,15,7]` দেয় 42 (15→20→7, root এড়িয়ে)। একক node `-3` দেয় -3 (নিতেই হবে), `[2,-1]` দেয় 2 (-1 arm বাদ), `[-2,-1]` দেয় -1 (কম খারাপ) — সব pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার করে visit হয় (n = node সংখ্যা)। প্রতিটা node-এ কাজ ধ্রুবক (দুটো max, একটা যোগ)। এর চেয়ে কম সম্ভব না — উত্তর জানতে প্রতিটা value অন্তত একবার দেখতেই হবে।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — recursion call stack tree-র height h সমান গভীর হয় (balanced হলে O(log n), skewed হলে O(n))। `best` একটা মাত্র scalar, তাই বাড়তি memory নগণ্য।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- ঋণাত্মক arm **না ছাঁটা** (`max(gain, 0)` ভুলে যাওয়া) — লোকসানি branch যোগ হয়ে উত্তর ছোট হয়ে যায়।
- `best`-কে `0` দিয়ে শুরু করা — সব-ঋণাত্মক tree-তে ভুল 0 দেয়; `-inf` লাগে কারণ অন্তত একটা node নিতেই হবে।
- parent-কে **দুই arm** যোগ করে ফেরত দেওয়া — তখন path দু'বার এক node ছুঁয়ে ফেলে; return-এ শুধু `max(left, right)`।
- global update আর return মান গুলিয়ে ফেলা — update দুই arm, return এক arm।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Diameter of Binary Tree (#18)-এর "height return করো, পাশে দুই-দিক যোগফল track করো" কাঠামো, আর Maximum Depth-এর postorder fold। height→gain আর "edge গোনা"→"value যোগ + ঋণাত্মক বাদ" — এই দুটো বদল করলেই Max Path Sum দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Diameter of Binary Tree (একই দুই-arm কাঠামো, কিন্তু value নয় edge গোনা) —