Problem link ও উৎস
- **Original source:** Classic tree height-with-side-channel exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Diameter via height
- **Basic idea inherited from:** Maximum Depth + side-channel update (এই tracker-এর #1)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree দেওয়া আছে। তোমার কাজ: এর **diameter** বের করা — যেকোনো দুটো node-এর মধ্যে সবচেয়ে লম্বা path-এ কতগুলো **edge** আছে, সেই সংখ্যা। এই path root-এর ভেতর দিয়ে নাও যেতে পারে।
```text
1
/ \
2 3 সবচেয়ে লম্বা path: 4 → 2 → 1 → 3 (অথবা 5 → 2 → 1 → 3)
/ \
4 5 3 edge → diameter = 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [1,2,3,4,5]
Output: 3 (path 4→2→1→3, 3 edge)
Input : root = [1,2] -> Output: 1 (এক edge)
Edge : root = [1] -> Output: 0 (একক node, কোনো edge নেই)
Edge : root = [] -> Output: 0 (খালি tree)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পাহাড়ি এলাকার সব শিখরের উচ্চতা মাপতে মাপতে তুমি এগোচ্ছ। প্রতিটা চূড়ায় দাঁড়িয়ে তুমি ভাবো "আমার দুই ঢালের সবচেয়ে দূরের দুই বিন্দুর মধ্যে দূরত্ব কত?" — সেটা একটা নোটবুকে (shared holder) টুকে রাখো যদি আগের চেয়ে বড় হয়। উপরে তুমি শুধু তোমার নিজের উচ্চতা রিপোর্ট করো, কিন্তু সবচেয়ে লম্বা বিস্তারটা নোটবুকে জমা থাকে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Maximum Depth** (#1)-এর postorder height-fold থেকে আসে, একটা **side-channel update** যোগ করে। Maximum Depth-এ প্রতিটা node তার height উপরে ফেরত দিত। এখানে একই height হিসাব করি, কিন্তু পথে পথে একটা shared "best diameter" variable-ও update করি। এক traversal, দুটো কাজ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো প্রতিটা node-এ একটা path-candidate মাপা:
```text
height(empty) = -1 (edge গোনা)
এই node-এর ভেতর দিয়ে path = left_height + right_height + 2 (edge সংখ্যা)
best = max(best, এই candidate)
height(node) = 1 + max(left_height, right_height) (উপরে শুধু height যায়)
```
প্রতিটা node ভাবে "আমার ভেতর দিয়ে সবচেয়ে লম্বা path কত?" — দুই দিকের height যোগ + 2 edge। সব node-এর candidate-এর সর্বোচ্চটাই diameter।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো বড় data structure লাগে না। **recursion call stack** (height bottom-up হিসাব করে) আর একটা ছোট **shared mutable holder** (এক-element list বা nonlocal variable) যাতে best diameter সব call জুড়ে update হতে পারে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Height হিসাব নিজেই একটা postorder recursion — call stack তা সামলায়। কিন্তু diameter পুরো tree-জুড়ে একটা চলমান max, তাই একটা shared holder লাগে যা প্রতিটা call থেকে লেখা যায়। এক-element list (`best[0]`) বা nonlocal এই "side channel"-টা দেয়, return value-কে শুধু height-এর জন্য মুক্ত রেখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা node-কে আলাদা করে ভাবি — "এই node-এর ভেতর দিয়ে সবচেয়ে লম্বা path" = বাঁ subtree-র height + ডান subtree-র height + 2। প্রতিটা node-এ এটা মাপি, সর্বোচ্চটা নিই।
```text
প্রতিটা node-এর জন্য:
lh = height(node.left) ← আলাদা পুরো traversal
rh = height(node.right) ← আলাদা পুরো traversal
candidate = lh + rh + 2
সব candidate-এর max = diameter
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই সরল রূপে প্রতিটা node-এ আলাদা করে `height()` ডাকা হয়, আর height নিজেই পুরো subtree ঘোরে। তাই একই height বারবার হিসাব হয় — মোট **O(n²)** (skewed tree-তে আরো খারাপ)। আসলে height আর diameter-update একই traversal-এ করা যায়, প্রতিটা subtree একবার ঘুরে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা postorder walk এমনিতেই সব height bottom-up হিসাব করে — তাই প্রতিটা node-এ height পাওয়ার ঠিক সেই মুহূর্তেই diameter-candidate (lh+rh+2) মাপা যায়, কোনো বাড়তি traversal ছাড়াই।** Return value height-এর জন্য, side-channel diameter-এর জন্য।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
এটা "**একটা জিনিস return করো, আরেকটা update করো**" pattern। একটা postorder `height` function: base-এ খালি subtree -1 (edge গোনা); প্রতিটা node-এ `best = max(best, lh + rh + 2)` দিয়ে diameter update; তারপর `1 + max(lh, rh)` height উপরে দাও। একবার tree ঘোরা — O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সবচেয়ে লম্বা path খুঁজে বের করব" ভাবা বন্ধ করো। বরং ভাবো "প্রতিটা node-কে জিজ্ঞেস করব: তোমার ভেতর দিয়ে গেলে path কত লম্বা?" — সেটা শুধু তার দুই দিকের height-এর যোগ। সব node-এর এই উত্তরের সর্বোচ্চটাই diameter। আর height তো এমনিতেই হিসাব হচ্ছে, তাই candidate পাশে free-তে পাওয়া যায়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা node-এ candidate = বাঁ height + ডান height + 2; best update হয়:
```text
1 lh=1 (2-এর দিক), rh=0 (3) → cand 1+0+2 = 3 ← best
/ \
lh=0,rh=0 2 3 (leaf, height 0)
/ \
4 5 (leaf, height 0)
node 2: cand = 0+0+2 = 2 ; node 1: cand = 1+0+2 = 3 → diameter 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1,2,3,4,5]`, `best = 0` শুরুতে:
1. `height(4)`: leaf → lh=-1, rh=-1, cand = -1+-1+2 = 0, best=0; height = 0।
2. `height(5)`: একই, height = 0, best=0।
3. `height(2)`: lh=0 (4), rh=0 (5), cand = 0+0+2 = 2, best=2; height = 1।
4. `height(3)`: leaf, height = 0, cand 0, best stays 2।
5. `height(1)`: lh=1 (2), rh=0 (3), cand = 1+0+2 = 3, best=3; height = 2।
6. উত্তর = best = **3**।
## কোড ও ব্যাখ্যা {#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 diameter_of_binary_tree(root):
best = [0] # shared side-channel (সব call জুড়ে)
def height(node):
if node is None: # খালি subtree: -1 (edge গোনা)
return -1
lh = height(node.left) # বাঁ দিকের height
rh = height(node.right) # ডান দিকের height
best[0] = max(best[0], lh + rh + 2) # এই node-এ বাঁকা path-এর edge
return 1 + max(lh, rh) # উপরে শুধু height যায়
height(root)
return best[0]
# ---- tests ----
assert diameter_of_binary_tree(build_tree([1, 2, 3, 4, 5])) == 3
assert diameter_of_binary_tree(build_tree([1, 2])) == 1
assert diameter_of_binary_tree(build_tree([1])) == 0
assert diameter_of_binary_tree(build_tree([])) == 0
assert diameter_of_binary_tree(build_tree([1, 2, None, 3, None, 4])) == 3
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `best = [0]` — এক-element list, একটা shared mutable holder; সব recursive call এতে লিখতে পারে।
- `if node is None: return -1` — খালি subtree-র height -1, কারণ আমরা edge গুনছি (node না)।
- `lh = height(node.left)` / `rh = height(node.right)` — দুই দিকের height bottom-up।
- `best[0] = max(best[0], lh + rh + 2)` — এই node-এর ভেতর দিয়ে যাওয়া path-এর edge সংখ্যা; running max update।
- `return 1 + max(lh, rh)` — উপরে শুধু নিজের height পাঠাও (পুরো diameter না)।
- `height(root); return best[0]` — traversal চালাও, তারপর জমা-হওয়া best ফেরত দাও।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_tree([1,2,3,4,5])` ওই ছবির tree বানায়; `diameter_of_binary_tree` 3 ফেরত দেয় (path 4→2→1→3) — assert pass। `[1,2]` দেয় 1, একক node দেয় 0, খালি tree দেয় 0, আর একপাশে-ঝোলা chain `[1,2,None,3,None,4]` দেয় 3 (3 edge) — সব pass। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val; this.left = left; this.right = right;
}
}
function buildTree(values) {
if (!values || values.length === 0) return null;
const root = new TreeNode(values[0]);
const q = [root];
let i = 1, head = 0;
while (head < q.length && i < values.length) {
const node = q[head++];
if (i < values.length && values[i] !== null) { node.left = new TreeNode(values[i]); q.push(node.left); }
i++;
if (i < values.length && values[i] !== null) { node.right = new TreeNode(values[i]); q.push(node.right); }
i++;
}
return root;
}
function diameterOfBinaryTree(root) {
let best = 0; // shared side-channel (closure)
const height = (node) => {
if (node === null) return -1; // খালি subtree: -1 (edge গোনা)
const lh = height(node.left); // বাঁ দিকের height
const rh = height(node.right); // ডান দিকের height
best = Math.max(best, lh + rh + 2); // এই node-এ বাঁকা path-এর edge
return 1 + Math.max(lh, rh); // উপরে শুধু height যায়
};
height(root);
return best;
}
// ---- test cases ----
assert(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])) === 3, "diameter 3");
assert(diameterOfBinaryTree(buildTree([1, 2])) === 1, "এক edge");
assert(diameterOfBinaryTree(buildTree([1])) === 0, "একক node");
assert(diameterOfBinaryTree(buildTree([])) === 0, "খালি tree");
assert(diameterOfBinaryTree(buildTree([1, 2, null, 3, null, 4])) === 3, "skewed chain");
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এ side-channel-এর জন্য এক-element list (`best[0]`) বা `nonlocal` লাগে; JS-এ আরও সহজ — একটা `let best` outer scope-এ রাখলে inner arrow-function closure দিয়ে সরাসরি reassign করতে পারে (`best = ...`)। কোনো mutable wrapper-এর দরকার নেই। `Math.max` plain number-এ কাজ করে, আর `-1` base case edge-গোনা convention।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }
function node(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
return { val, left, right };
}
function buildTree(values: (number | null)[]): TreeNode | null {
if (values.length === 0) return null;
const root = node(values[0] as number);
const q: TreeNode[] = [root];
let i = 1, head = 0;
while (head < q.length && i < values.length) {
const cur = q[head++];
if (i < values.length && values[i] !== null) { cur.left = node(values[i] as number); q.push(cur.left); }
i++;
if (i < values.length && values[i] !== null) { cur.right = node(values[i] as number); q.push(cur.right); }
i++;
}
return root;
}
function diameterOfBinaryTree(root: TreeNode | null): number {
let best = 0;
const height = (n: TreeNode | null): number => {
if (n === null) return -1;
const lh = height(n.left);
const rh = height(n.right);
best = Math.max(best, lh + rh + 2);
return 1 + Math.max(lh, rh);
};
height(root);
return best;
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
expect(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])) === 3, "3");
expect(diameterOfBinaryTree(buildTree([1, 2])) === 1, "1");
expect(diameterOfBinaryTree(buildTree([1])) === 0, "0");
expect(diameterOfBinaryTree(buildTree([])) === 0, "খালি");
expect(diameterOfBinaryTree(buildTree([1, 2, null, 3, null, 4])) === 3, "chain");
console.log("সব TS test pass!");
```
> **TS টীকা:** `let best = 0` থেকে TS নিজেই infer করে `best` একটা `number`, তাই inner `height`-এ `best = Math.max(...)` type-safe থাকে। `height`-এর return type `number` স্পষ্ট করে দেয় — উপরে সবসময় height (একটা সংখ্যা) যায়, কখনো ভুল করে diameter বা অন্য কিছু না। এই দুই দায়িত্ব (return height, update best) পরিষ্কারভাবে আলাদা থাকে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার করে visit হয় (n = node সংখ্যা)। side-channel update O(1), তাই brute force-এর O(n²) থেকে নেমে O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — recursion call stack tree-র height h সমান গভীর। Balanced tree-তে O(log n), skewed chain-এ O(n)। `best` holder O(1)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- খালি subtree-তে 0 ফেরত দেওয়া (node-গোনা convention) — তখন edge সংখ্যা ভুল আসে; এই edge-গোনা সূত্রে -1 দরকার।
- diameter হিসেবে height ফেরত দেওয়া — height আর diameter আলাদা; diameter side-channel-এ জমে, return-এ না।
- প্রতিটা node-এ আলাদা `height()` ডেকে O(n²) করে ফেলা — একই traversal-এ দুটো কাজ করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Maximum Depth (#1)-এর postorder height-fold আর traversal-patterns.md-র Pattern E (diameter via height)। "এক জিনিস return, আরেক জিনিস update" — এই ভাগটাই মূল শিক্ষা।
### পরের অনুশীলন {#22-similar-harder-problems}
- Binary Tree Maximum Path Sum (একই bend-pattern, edge-এর জায়গায় value, negative pruning সহ) —