015 — Kth Smallest Element in a BST¶

Source¶

Original source: Classic BST inorder-traversal exercise
Platform: LeetCode — https://leetcode.com/problems/kth-smallest-element-in-a-bst/
Topic: trees
Difficulty: Medium
Pattern: Inorder = sorted
Basic idea inherited from: Inorder traversal + early stop — BST-তে inorder মানেই sorted order

1. Problem in simple words¶

তোমাকে একটা Binary Search Tree আর একটা সংখ্যা k দেওয়া আছে। তোমার কাজ: tree-র সব value-র মধ্যে k-তম সবচেয়ে ছোট value-টা বের করা (k এখানে 1-থেকে গোনা — অর্থাৎ k=1 মানে সবচেয়ে ছোট)।

        5
       / \
      3   8        sorted order: 1, 3, 4, 5, 8, 9
     / \   \
    1   4   9      k=3 → 3-তম ছোট = 4

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 দুই অংশ:

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/-এর একটা 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 পরিষ্কার।

6. Real-life analogy¶

একটা sorted ফাইল-ক্যাবিনেট ভাবো, যেখানে inorder traversal মানে বাঁ থেকে ডানে folder-গুলো ক্রমে খোলা। তুমি গুনতে গুনতে এগোও: 1, 2, 3... k-তম folder খুলেই থেমে যাও — পুরো ক্যাবিনেট ঘাঁটার দরকার নেই, কারণ সব আগেই sorted।

7. Visual explanation¶

inorder visit-এর ক্রম (নিচের সংখ্যা = visit order); k=3-এ থামি:

        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

8. Example input and output¶

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: পুরো tree-র সব value একটা list-এ জমাই (যেকোনো traversal-এ), তারপর list-টা sort করে [k-1] index তুলি।

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-তম পেয়ে গেলেই থেমে যাও। সমস্যাটা "ঘুরতে ঘুরতে গোনা আর সময়মতো থামা"-তে গলে যায়।

14. Step-by-step dry run¶

Input tree [5,3,8,1,4,null,9], k = 3 (iterative stack):

5 থেকে বাঁয়ে নামো: push 5, push 3, push 1। stack [5, 3, 1]।
pop 1 → 1st smallest। k=3, এখনো না। 1-এর ডান নেই।
pop 3 → 2nd smallest। এখনো না। 3-এর ডানে 4 → push 4। stack [5, 4]।
pop 4 → 3rd smallest। k=3 হয়ে গেছে → উত্তর 4, থামো।

15. Python solution¶

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-র পালা।

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!।

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 দেয়।

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 যাচাই) — https://leetcode.com/problems/validate-binary-search-tree/ (এই tracker-এর #14)
Kth Largest Element in a Stream (running k-th, heap দিয়ে) — https://leetcode.com/problems/kth-largest-element-in-a-stream/
Two Sum IV - Input is a BST (inorder + two-pointer / set) — https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

23. Pattern learned¶

Inorder-with-early-stop: BST-তে sorted order চাইলে inorder করো, আর শুধু যতটুকু দরকার ততটুকু ঘুরে থেমে যাও। k-তম smallest হলো এর আদর্শ রূপ — sort করার দরকার নেই, কারণ structure-টাই sorted, আর গণনা শেষ হলেই থামা যায়।

24. Final summary¶

ভবিষ্যতের আমাকে: "BST-তে k-তম ছোট = inorder-এ k-তম visit, k পেলেই থামো।" Inorder ছাড়া অন্য order এখানে কাজ করে না, আর sort করার দরকারও নেই। BST + 'sorted-order কিছু চাই' দেখলেই এই inorder চালটা মনে করবে।

25. JavaScript solution (with test cases)¶

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 নিরাপদ।

26. TypeScript solution (with test cases)¶

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 করতে আপত্তি করত।

27. কোথায় কাজে লাগে (real-world use)¶

Leaderboard / ranking query: একটা sorted structure (BST/index) থেকে "k-তম সেরা স্কোর" বা "k-তম সস্তা দাম" দ্রুত বের করা, পুরো list sort না করেই।
Database ORDER BY ... LIMIT/OFFSET: sorted index-এ নির্দিষ্ট rank থেকে কয়েকটা row নেওয়া — pagination-এর ভিত্তি।
Percentile / median estimation: sorted data-তে নির্দিষ্ট position-এর value (যেমন median = মাঝের element) পেতে inorder + counter।
Order statistics: "k-তম ক্ষুদ্রতম দূরত্ব", "k-তম পুরোনো record" — যেকোনো rank-ভিত্তিক query যেখানে data ইতিমধ্যে sorted।
Streaming top/bottom-k near a pivot: BST-তে maintain করা data থেকে একটা নির্দিষ্ট rank-এর আশেপাশের value early-stop সহ বের করা।

মূল সুর: data ইতিমধ্যে sorted-structure-এ থাকলে নির্দিষ্ট rank পেতে আর sort কোরো না — inorder-এ গুনতে গুনতে এগিয়ে সময়মতো থেমে যাও।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।