002 — Binary Tree Inorder Traversal¶

Source¶

Original source: Classic tree traversal exercise
Platform: LeetCode — https://leetcode.com/problems/binary-tree-inorder-traversal/
Topic: trees
Difficulty: Easy
Pattern: Traversal order
Basic idea inherited from: traversal-patterns.md-র DFS trio — তিন visit order-এর মধ্যে inorder

1. Problem in simple words¶

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: সব node-এর value একটা list-এ ফেরত দাও, কিন্তু একটা নির্দিষ্ট ক্রমে — inorder, মানে Left → Node → Right।

প্রতিটা node-এ নিয়ম এক: আগে পুরো বাঁ-দিক সারো, তারপর নিজের value নাও, তারপর পুরো ডান-দিক সারো।

1
 \
  2
 /
3        ← inorder = [1, 3, 2]

2. Which basic idea does this inherit from?¶

এটা traversal-patterns.md-র DFS trio-র (in/pre/post) প্রথমজন। তিনজনেই একই recursion কঙ্কাল ব্যবহার করে — শুধু "নিজের value কখন নেব" সেই মুহূর্তটা আলাদা। inorder-এ value নেওয়া হয় দুই recursive call-এর মাঝখানে sandwich করে।

3. What is the hidden math or logic?¶

লুকানো logic হলো একটা ক্রমের সংজ্ঞা নিজেই:

inorder(empty) = []
inorder(node)  = inorder(node.left) + [node.val] + inorder(node.right)

এই sandwich-এর একটা superpower আছে: tree-টা যদি BST হয় (concept.md দেখো), inorder ঠিক sorted ascending order-এ value বের করে দেয়। কারণ বাঁ-দিক সবসময় ছোট, ডান-দিক সবসময় বড়।

4. Which data structure is needed?¶

একটা output list (জমা করার জন্য) আর recursion call stack (কোন path-এ আছি মনে রাখতে)। চাইলে recursion-এর বদলে একটা explicit stack-ও ব্যবহার করা যায় (../../04-stack-and-queue/), কিন্তু recursion-টা সবচেয়ে পরিষ্কার।

5. Why this data structure fits¶

Tree self-similar, তাই recursion প্রতিটা subtree-কে আলাদা ছোট tree হিসেবে সামলায়। call stack এমনিতেই "left নামলাম, এখন উপরে উঠে value নেব, তারপর right" — এই ফেরার পথটা মনে রাখে। output list শুধু সঠিক ক্রমে value জড়ো করে।

6. Real-life analogy¶

একটা গাছে বাঁ থেকে ডানে ঝোলানো বই-এর তাক ভাবো। তুমি সবচেয়ে বাঁয়ের গভীরতম তাক থেকে পড়া শুরু করো, তারপর তার ঠিক উপরের তাক, তারপর ডানে সরো। সবসময় "যতটা বাঁয়ে যাওয়া যায় যাও, তারপর পড়ো, তারপর ডানে।" — সাজানো একটা library-র মতো বেরিয়ে আসে।

7. Visual explanation¶

তীরগুলো recursion-এর ক্রম; ★ মানে এই মুহূর্তে value নেওয়া হলো (Left শেষ হওয়ার পর, Right শুরুর আগে):

        4
       / \
      2   6
     / \ / \
    1  3 5  7

হাঁটা: 1★ → 2★ → 3★ → 4★ → 5★ → 6★ → 7★
inorder = [1, 2, 3, 4, 5, 6, 7]   (BST হলে sorted!)

8. Example input and output¶

Input : root = [1,null,2,3]
Output: [1, 3, 2]

Input : root = []        -> Output: []     (খালি tree)
Input : root = [1]       -> Output: [1]    (একটা node)

9. Brute force thinking¶

"Traversal" নিজেই মূল কাজ, তাই brute force বলতে এখানে বোঝায় iterative ভাবে নিজের হাতে stack চালানো — recursion-কে অবিশ্বাস করে প্রতিটা node manually push/pop করা।

1) যতদূর বাঁয়ে যাওয়া যায় যাও, প্রতিটা node stack-এ রাখো
2) stack থেকে pop করো → তার value নাও
3) তার right-এ যাও, আবার ধাপ 1

10. Why brute force is slow¶

Iterative version slow না (একই O(n)), কিন্তু লিখতে ও বুঝতে কঠিন — কখন push, কখন pop, কখন right-এ সরব, সব হাতে সামলাতে হয়। recursion সেই সব book-keeping নিজেই করে দেয়, তাই কম bug, পরিষ্কার code। (iterative version লাগে শুধু খুব গভীর tree-তে recursion limit এড়াতে।)

11. Key observation¶

মূল observation: value নেওয়ার মুহূর্তটাই পুরো খেলা। inorder = বাঁ-call আর ডান-call-এর মাঝে value নাও। এই এক লাইন সরালেই (উপরে নিলে preorder, নিচে নিলে postorder) সম্পূর্ণ ভিন্ন ক্রম পাও।

12. Optimized intuition¶

তিন লাইনের recursion: বাঁয়ে নামো, এই node-এর value append করো, ডানে নামো। base case-এ None হলে চুপচাপ ফিরে যাও। একবার পুরো tree ঘোরা — প্রতিটা node ঠিক একবার append হয়।

13. Thinking tweak¶

মোচড়: তিনটা traversal আলাদা করে মুখস্থ কোরো না। একটাই কঙ্কাল মনে রাখো — "left, [এখানে কোথাও value নাও], right" — আর শুধু value নেওয়ার লাইনটা কোথায় বসছে সেটা ভাবো। inorder মানে লাইনটা ঠিক মাঝখানে।

14. Step-by-step dry run¶

Input [1,null,2,3] (tree: 1-এর right 2, 2-এর left 3):

visit(1): left = None → চুপচাপ ফিরল। এখন append 1। out = [1]।
visit(1.right = 2): আগে left।
visit(2.left = 3): left None → append 3। out = [1, 3]। right None → ফিরল।
উপরে উঠে append 2। out = [1, 3, 2]। 2-এর right None → ফিরল।
সব শেষ → [1, 3, 2]।

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 inorder_traversal(root):
    out = []

    def visit(node):
        if node is None:        # base case: খালি subtree, কিছু নেই
            return
        visit(node.left)        # 1) আগে পুরো বাঁ-দিক
        out.append(node.val)    # 2) তারপর নিজের value (sandwich-এর মাঝে)
        visit(node.right)       # 3) তারপর পুরো ডান-দিক

    visit(root)
    return out


# ---- tests ----
assert inorder_traversal(build_tree([1, None, 2, 3])) == [1, 3, 2]
assert inorder_traversal(build_tree([])) == []
assert inorder_traversal(build_tree([1])) == [1]
# BST হলে inorder sorted আসে:
assert inorder_traversal(build_tree([4, 2, 6, 1, 3, 5, 7])) == [1, 2, 3, 4, 5, 6, 7]
print("সব test pass!")

16. Line-by-line code explanation¶

out = [] — সঠিক ক্রমে value জমানোর জায়গা।
def visit(node) — ভেতরের helper; out-কে closure দিয়ে ধরে রাখে।
if node is None: return — base case; খালি subtree থেকে কিছু যোগ হয় না।
visit(node.left) — আগে বাঁ-জগৎ সম্পূর্ণ সারো।
out.append(node.val) — মূল চাল: value নেওয়া হয় ঠিক মাঝখানে।
visit(node.right) — তারপর ডান-জগৎ।
return out — পুরো inorder sequence।

17. Output walkthrough¶

[1,null,2,3] → [1, 3, 2] (dry run-এর সাথে মেলে)। খালি tree → []; একক node → [1]; BST [4,2,6,1,3,5,7] → [1,2,3,4,5,6,7] (sorted, কারণ inorder + BST)। সব assert pass, শেষে print: সব test pass!।

18. Time complexity¶

O(n) — প্রতিটা node ঠিক একবার visit আর একবার append হয়।

19. Space complexity¶

O(n) output list-এর জন্য; recursion stack আলাদাভাবে O(h) (h = height) — concept.md-র table অনুযায়ী balanced-এ O(log n), chain-এ O(n)।

20. Common mistakes¶

value নেওয়ার লাইন ভুল জায়গায় বসিয়ে অজান্তে preorder/postorder বানিয়ে ফেলা।
left আর right call উল্টে দেওয়া → ক্রম উল্টে যায়।
base case বাদ দিয়ে None.left ছোঁয়া → AttributeError।

21. Which basic problem this inherits from¶

ভিত্তি: traversal-patterns.md-র DFS trio-র inorder sketch আর concept.md-র recursion ভিত্তি। এই sandwich বুঝলে preorder/postorder শুধু এক লাইন সরানোর ব্যাপার।

22. Similar harder problems¶

Binary Tree Preorder Traversal (value নেওয়া আগে) — https://leetcode.com/problems/binary-tree-preorder-traversal/ (এই tracker-এর #3)
Kth Smallest Element in a BST (inorder + k-টা visit-এর পর থামো) — https://leetcode.com/problems/kth-smallest-element-in-a-bst/ (#15)
Validate Binary Search Tree (inorder কঠোরভাবে increasing কিনা) — https://leetcode.com/problems/validate-binary-search-tree/ (#14)

23. Pattern learned¶

DFS visit-order: একটাই recursion কঙ্কাল (left / value / right), value-নেওয়ার মুহূর্তটাই ক্রম ঠিক করে। inorder = মাঝখানে; BST-তে এটা sorted দেয় — অনেক BST problem-এর গোপন চাবি।

24. Final summary¶

ভবিষ্যতের আমাকে: "inorder = Left, নিজে, Right — value নেওয়া sandwich-এর মাঝখানে।" BST-র কথা শুনলেই inorder-এর কথা ভাববে, কারণ এটা চুপচাপ sorted order এনে দেয়। তিন traversal একসাথে মনে রাখার চাবি: শুধু value-নেওয়ার লাইনটা কোথায়।

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;
  }
}

// level-order array (null = missing child) থেকে tree বানায়
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 inorderTraversal(root) {
  const out = [];
  const visit = (node) => {
    if (node === null) return;   // base case: খালি subtree
    visit(node.left);            // 1) আগে পুরো বাঁ-দিক
    out.push(node.val);          // 2) তারপর নিজের value (sandwich-এর মাঝে)
    visit(node.right);           // 3) তারপর পুরো ডান-দিক
  };
  visit(root);
  return out;
}

// JSON.stringify দিয়ে array সমতা যাচাই করি (সহজ deep-equal)
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);

// ---- test cases ----
assert(eq(inorderTraversal(buildTree([1, null, 2, 3])), [1, 3, 2]), "basic");
assert(eq(inorderTraversal(buildTree([])), []), "খালি");
assert(eq(inorderTraversal(buildTree([1])), [1]), "একক node");
// BST হলে inorder sorted আসে:
assert(eq(inorderTraversal(buildTree([4, 2, 6, 1, 3, 5, 7])), [1, 2, 3, 4, 5, 6, 7]), "BST sorted");
console.log("সব JS test pass!");

JS টীকা: JS-এ array সমতা === দিয়ে হয় না (reference তুলনা করে), তাই JSON.stringify দিয়ে দুই array deep-compare করেছি — সংখ্যার array-তে এটা নিরাপদ ও সহজ। out.push Python-এর list.append-এর সমতুল্য। inner visit একটা closure, যা বাইরের out-কে ধরে রাখে — Python-এর nested function-এর মতোই।

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 inorderTraversal(root: TreeNode | null): number[] {
  const out: number[] = [];
  const visit = (n: TreeNode | null): void => {
    if (n === null) return;
    visit(n.left);
    out.push(n.val);
    visit(n.right);
  };
  visit(root);
  return out;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a: number[], b: number[]): boolean => a.length === b.length && a.every((v, i) => v === b[i]);

expect(eq(inorderTraversal(buildTree([1, null, 2, 3])), [1, 3, 2]), "basic");
expect(eq(inorderTraversal(buildTree([])), []), "খালি");
expect(eq(inorderTraversal(buildTree([1])), [1]), "একক");
expect(eq(inorderTraversal(buildTree([4, 2, 6, 1, 3, 5, 7])), [1, 2, 3, 4, 5, 6, 7]), "BST");
console.log("সব TS test pass!");

TS টীকা: return type number[] স্পষ্ট করে দেয় function সবসময় সংখ্যার array দেয়, কখনো undefined না। out: number[] typed array-তে ভুল করে string push করলে compile-time error। এখানে eq helper-টা .every দিয়ে element-wise তুলনা করে — typed হওয়ায় index access নিরাপদ।

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

BST থেকে sorted data বের করা: কোনো database index (প্রায়ই B-tree/BST) থেকে key-গুলো sorted order-এ পড়তে inorder traversal-ই ব্যবহৃত হয় — range query বা ordered scan-এ।
Expression tree evaluation: গণিত expression-কে tree-তে রাখলে inorder traversal infix form (a + b * c) ফিরিয়ে দেয় — calculator আর compiler-এ।
Auto-complete / dictionary: sorted শব্দ-তালিকা একটা BST-তে রাখলে inorder দিয়ে alphabetical order-এ সব শব্দ বা একটা range বের করা যায়।
Syntax highlighting / code formatting: abstract syntax tree (AST) ঘুরে source code পুনর্গঠন করতে নির্দিষ্ট traversal order দরকার হয়।
"k-th smallest" / median খোঁজা: sorted structure-এ নির্দিষ্ট rank-এর element পেতে inorder + counter কাজে লাগে (এই tracker-এর #15)।

মূল সুর: যখনই hierarchical data-কে একটা নির্দিষ্ট রৈখিক ক্রমে (বিশেষত sorted) দেখতে হবে, inorder traversal হলো সেই sandwich-চাবি।

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