002 — Binary Tree Inorder Traversal¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

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

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

উদাহরণ

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

Input ও output¶

উদাহরণ

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

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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

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

ভেতরের যুক্তি¶

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

উদাহরণ

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

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

কী দিয়ে তথ্য রাখব¶

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

এটি কেন উপযুক্ত¶

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

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

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

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে¶

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

যে বিষয়টি খেয়াল করতে হবে¶

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

আরও কম কাজে সমাধান¶

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

ভাবনার পরিবর্তন¶

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

ছবিতে বোঝা¶

তীরগুলো 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!)

ছোট input-এ ধাপে ধাপে¶

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

কোড ও ব্যাখ্যা¶

Python¶

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 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!")

কোডের প্রতিটি অংশ¶

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।

Output মিলিয়ে দেখা¶

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

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

// 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-এর মতোই।

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

খরচ ও সাধারণ ভুল¶

সময়¶

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

অতিরিক্ত জায়গা¶

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

যে ভুলগুলো এড়াতে হবে¶

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

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

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

পরের অনুশীলন¶

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)

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

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

কোথায় কাজে লাগে¶

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।