Problem link ও উৎস
- **Original source:** Classic BST inorder-traversal exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Inorder = sorted
- **Basic idea inherited from:** Inorder traversal + early stop — BST-তে inorder মানেই sorted order
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **Binary Search Tree** আর একটা সংখ্যা `k` দেওয়া আছে। তোমার কাজ: tree-র সব value-র মধ্যে **k-তম সবচেয়ে ছোট** value-টা বের করা (k এখানে 1-থেকে গোনা — অর্থাৎ k=1 মানে সবচেয়ে ছোট)।
```text
5
/ \
3 8 sorted order: 1, 3, 4, 5, 8, 9
/ \ \
1 4 9 k=3 → 3-তম ছোট = 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [5,3,8,1,4,null,9], k = 3
Output: 4
Input : root = [5,3,8,1,4,null,9], k = 1 -> Output: 1 (সবচেয়ে ছোট)
Input : root = [5,3,8,1,4,null,9], k = 6 -> Output: 9 (সবচেয়ে বড়)
Edge : root = [1], k = 1 -> Output: 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা sorted ফাইল-ক্যাবিনেট ভাবো, যেখানে inorder traversal মানে বাঁ থেকে ডানে folder-গুলো ক্রমে খোলা। তুমি গুনতে গুনতে এগোও: 1, 2, 3... k-তম folder খুলেই থেমে যাও — পুরো ক্যাবিনেট ঘাঁটার দরকার নেই, কারণ সব আগেই sorted।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **inorder traversal**-এর সেই superpower থেকে আসে (traversal-patterns.md দেখো): BST-তে inorder (Left → Node → Right) মানেই value-গুলো **sorted ascending order**-এ বের হওয়া। তাই k-তম ছোট মানে inorder-এ k-তম visit করা node। সাথে যোগ হয় recursion-এর **early stop** — k-তম পেয়ে গেলে বাকিটা ঘোরার দরকার নেই।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই অংশ:
```text
1) BST + inorder = sorted ascending sequence
2) সেই sequence-এর k-তম element (1-indexed) = উত্তর
```
মানে আমরা পুরো tree sort করি না; inorder traversal এমনিতেই sorted order দেয়, তাই শুধু visit গুনে k-তম-তে থামলেই হলো।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো বিকল্প: (a) **recursion call stack** দিয়ে inorder, একটা counter সহ; বা (b) [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-এর একটা **explicit stack** দিয়ে iterative inorder, যেটা k-তম-তে natural-ভাবে থেমে যায়। কোনো বড় extra structure লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Inorder-এর জন্য আমাদের "যত বাঁয়ে যাওয়া যায়, পথটা মনে রেখে" নামতে হয় — এটাই stack-এর কাজ (LIFO: সবচেয়ে গভীর unvisited আগে)। Iterative stack version-এ আমরা চাইলে exactly k-তম pop করে থেমে যেতে পারি, বাকি tree না ছুঁয়ে — early stop পরিষ্কার।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: পুরো tree-র সব value একটা list-এ জমাই (যেকোনো traversal-এ), তারপর list-টা sort করে `[k-1]` index তুলি।
```text
1) সব value জমাও: [5, 3, 1, 4, 8, 9]
2) sort করো: [1, 3, 4, 5, 8, 9]
3) উত্তর = sorted[k-1] = sorted[2] = 4
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
আলাদা করে sort করলে O(n log n) লাগে, যেখানে BST আমাদের sorted order বিনামূল্যে দিচ্ছে। আবার পুরো list বানানো আর পুরোটা sort করা অপচয় — আমরা তো শুধু k-তম চাই। Inorder + early stop শুধু প্রথম k node ছুঁয়েই থামে, গড়ে অনেক কম কাজ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **BST-তে inorder traversal value-গুলোকে sorted ascending order-এ বের করে।** তাই "k-তম সবচেয়ে ছোট" = "inorder-এ k-তম visit করা node।" এর মানে sort করার দরকারই নেই — শুধু inorder-এ visit গুনে k-তে থামো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
এটা একটা **inorder with early stop**। iterative version: একটা stack-এ যত বাঁয়ে যাওয়া যায় push করতে করতে নামো; তারপর pop করো (এটাই পরের sorted value), counter কমাও; counter 0 হলে সেই value-ই উত্তর — থামো; না হলে ডানে গিয়ে আবার বাঁয়ে নামো। প্রথম k node-এর পরই থেমে যায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "tree-টা sort করতে হবে" ভাবা বন্ধ করো — BST ইতিমধ্যেই sorted, শুধু inorder চোখে। আর "পুরোটা ঘুরতে হবে" ভাবাও বন্ধ করো — k-তম পেয়ে গেলেই থেমে যাও। সমস্যাটা "ঘুরতে ঘুরতে গোনা আর সময়মতো থামা"-তে গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
inorder visit-এর ক্রম (নিচের সংখ্যা = visit order); k=3-এ থামি:
```text
5 (4th)
/ \
3 8 (5th)
/ \ \
1 4 9 (6th)
(1st)(3rd)
↑ 2nd = 3, 3rd = 4 ← এখানে থামো (k=3)
visit order: 1, 3, 4, 5, 8, 9
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input tree `[5,3,8,1,4,null,9]`, `k = 3` (iterative stack):
1. 5 থেকে বাঁয়ে নামো: push 5, push 3, push 1। stack `[5, 3, 1]`।
2. pop 1 → 1st smallest। k=3, এখনো না। 1-এর ডান নেই।
3. pop 3 → 2nd smallest। এখনো না। 3-এর ডানে 4 → push 4। stack `[5, 4]`।
4. pop 4 → 3rd smallest। **k=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 kth_smallest(root, k):
stack, node = [], root # iterative inorder (../../04-stack-and-queue/)
while node or stack:
while node: # যত বাঁয়ে যাওয়া যায় নামো,
stack.append(node) # পথটা stack-এ মনে রেখে
node = node.left
node = stack.pop() # সবচেয়ে গভীর unvisited = পরের sorted value
k -= 1 # একটা visit হলো
if k == 0: # k-তম পেয়ে গেছি?
return node.val # থামো
node = node.right # তারপর ডান দিকে যাও
return -1 # (valid k হলে এখানে পৌঁছানোর কথা না)
# ---- tests ----
root = build_tree([5, 3, 8, 1, 4, None, 9])
assert kth_smallest(root, 3) == 4
assert kth_smallest(root, 1) == 1
assert kth_smallest(root, 6) == 9
assert kth_smallest(build_tree([1]), 1) == 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack, node = [], root` — explicit stack আর বর্তমান pointer, root দিয়ে শুরু।
- `while node: stack.append(node); node = node.left` — যতদূর বাঁয়ে যাওয়া যায়, পথ stack-এ জমিয়ে নামো।
- `node = stack.pop()` — সবচেয়ে গভীর unvisited node, যা inorder-এ পরের (সবচেয়ে ছোট বাকি) value।
- `k -= 1` — একটা node visit করা হলো।
- `if k == 0: return node.val` — ঠিক k-তম visit-এ থামো, এটাই উত্তর।
- `node = node.right` — এই node শেষ, এবার তার ডান subtree-র পালা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_tree([5,3,8,1,4,None,9])` ওই BST বানায়; `kth_smallest(root, 3)` 4 ফেরত দেয় — assert pass। k=1 দেয় 1 (সবচেয়ে ছোট), k=6 দেয় 9 (সবচেয়ে বড়), একক node দেয় 1 — সব 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 kthSmallest(root, k) {
const stack = []; // explicit stack দিয়ে iterative inorder
let node = root;
while (node !== null || stack.length > 0) {
while (node !== null) { // যত বাঁয়ে যাওয়া যায় নামো,
stack.push(node); // পথটা stack-এ মনে রেখে
node = node.left;
}
node = stack.pop(); // সবচেয়ে গভীর unvisited = পরের sorted value
k -= 1; // একটা visit হলো
if (k === 0) return node.val; // k-তম পেয়ে গেছি? থামো
node = node.right; // তারপর ডান দিকে যাও
}
return -1; // valid k হলে এখানে পৌঁছানোর কথা না
}
// ---- test cases ----
const root = buildTree([5, 3, 8, 1, 4, null, 9]);
assert(kthSmallest(root, 3) === 4, "k=3");
assert(kthSmallest(root, 1) === 1, "সবচেয়ে ছোট");
assert(kthSmallest(root, 6) === 9, "সবচেয়ে বড়");
assert(kthSmallest(buildTree([1]), 1) === 1, "একক node");
console.log("সব JS test pass!");
```
> **JS টীকা:** JS-এ array-ই double-duty stack হিসেবে কাজ করে — `push`/`pop` দুটোই O(1) আর LIFO, ঠিক Python-এর list-stack-এর মতো। iterative inorder-এ আলাদা library লাগে না। `node !== null` check গুরুত্বপূর্ণ, কারণ JS-এ `0`-valued node truthy/falsy গুলিয়ে যেতে পারে যদি `if (node)` লিখি; তাই স্পষ্ট `!== null` নিরাপদ।
### 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 kthSmallest(root: TreeNode | null, k: number): number {
const stack: TreeNode[] = [];
let node: TreeNode | null = root;
while (node !== null || stack.length > 0) {
while (node !== null) {
stack.push(node);
node = node.left;
}
node = stack.pop() as TreeNode; // loop-শর্ত নিশ্চিত করে stack অখালি
k -= 1;
if (k === 0) return node.val;
node = node.right;
}
return -1;
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const root = buildTree([5, 3, 8, 1, 4, null, 9]);
expect(kthSmallest(root, 3) === 4, "k=3");
expect(kthSmallest(root, 1) === 1, "min");
expect(kthSmallest(root, 6) === 9, "max");
expect(kthSmallest(buildTree([1]), 1) === 1, "একক");
console.log("সব TS test pass!");
```
> **TS টীকা:** `stack: TreeNode[]` typed হওয়ায় `stack.pop()`-এর type হয় `TreeNode | undefined`; কিন্তু আমাদের loop-শর্ত (`stack.length > 0`) নিশ্চিত করে এটা কখনো `undefined` হবে না, তাই `as TreeNode` দিয়ে compiler-কে জানাই। `node: TreeNode | null` স্পষ্ট type-annotation দরকার, না হলে TS প্রথমে `root`-এর type ধরে নিয়ে পরে `node.right` (যা null হতে পারে) assign করতে আপত্তি করত।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(h + k)** — উত্তর-leaf পর্যন্ত নামতে height h, তারপর k-তম পর্যন্ত k-টা node। সবচেয়ে খারাপ ক্ষেত্রে (skewed বা বড় k) O(n)। পুরো tree sort করার O(n log n)-এর চেয়ে ভালো।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — stack-এ সবচেয়ে বেশি একটা root-to-leaf পথ থাকে, যা height h। Balanced tree-তে O(log n), skewed-এ O(n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- k-কে 0-indexed ভাবা — এই problem 1-indexed, তাই k=1 মানে সবচেয়ে ছোট।
- early stop না করে পুরো inorder করা — ঠিক উত্তর দেয় কিন্তু অপ্রয়োজনে ধীর।
- preorder/postorder দিয়ে চেষ্টা করা — শুধু **inorder**-ই BST-তে sorted order দেয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: traversal-patterns.md-র inorder snippet আর Pattern C (BST property)। "BST + inorder = sorted" নিয়মটা বুঝলেই k-তম খোঁজা একটা সরল গোনা-আর-থামা কাজ হয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Validate Binary Search Tree (একই inorder, কিন্তু strictly increasing যাচাই) —