Tree — পরিভাষা, উপস্থাপন আর traversal

১ · Tree কী — পরিবার, ফোল্ডার আর সরকারি দপ্তরের ক্রমবিন্যাস

এ পর্যন্ত এই কোর্সে যত ডেটা স্ট্রাকচার দেখেছেন — array, linked list, stack, queue — সবই লাইনের মতো: প্রতিটি উপাদানের আগে একজন, পরে একজন। কিন্তু পৃথিবীর অনেক তথ্য লাইনে সাজানো থাকে না, থাকে ধাপে ধাপে ভাগ হয়ে। দাদার কয়েকজন ছেলেমেয়ে, তাঁদের প্রত্যেকের আবার ছেলেমেয়ে — একটি বংশতালিকা (family tree). আপনার কম্পিউটারের D: ড্রাইভে কয়েকটি ফোল্ডার, প্রতিটির ভেতরে আবার ফোল্ডার আর ফাইল। এ রকম “ওপর থেকে নিচে ভাগ হওয়া” কাঠামোকে বলে ক্রমবিন্যাস বা hierarchy, আর এর ডেটা স্ট্রাকচারের নাম tree (ট্রি).

একটি সরকারি উদাহরণ ভাবুন। প্রাথমিক ও গণশিক্ষা মন্ত্রণালয়ের অধীনে প্রাথমিক শিক্ষা অধিদপ্তর; অধিদপ্তরের অধীনে প্রতিটি জেলায় জেলা প্রাথমিক শিক্ষা অফিস; আর প্রতিটি জেলা অফিসের অধীনে কয়েকটি উপজেলা শিক্ষা অফিস। একটি নির্দেশ মন্ত্রণালয় থেকে নিচে নামে, আর প্রতিবেদন উপজেলা থেকে ওপরে ওঠে — কিন্তু কোনো উপজেলা অফিস একসাথে দুটি জেলা অফিসের অধীনে থাকে না। এই “প্রত্যেকের ঠিক একজন ঊর্ধ্বতন” নিয়মটিই tree-র প্রাণ।

প্রাথমিক ও গণশিক্ষা মন্ত্রণালয়                ← root
└── প্রাথমিক শিক্ষা অধিদপ্তর
    ├── জেলা প্রাথমিক শিক্ষা অফিস, রাজশাহী
    │   ├── উপজেলা শিক্ষা অফিস, পবা           ← leaf
    │   └── উপজেলা শিক্ষা অফিস, গোদাগাড়ী      ← leaf
    └── জেলা প্রাথমিক শিক্ষা অফিস, সিলেট
        └── উপজেলা শিক্ষা অফিস, জৈন্তাপুর       ← leaf

প্রোগ্রামিংয়ের জগতে tree প্রায় সবখানে। Windows Explorer-এর বাঁ পাশের ফোল্ডার-গাছ একটি tree. একটি ওয়েবপেজ খুললে ব্রাউজার HTML পড়ে একটি tree বানায়, যার নাম DOM (Document Object Model): <html>-এর নিচে <head> আর <body>, <body>-এর নিচে <div>, তার নিচে <p>. JSON ফাইল, কম্পাইলারের কাছে আপনার কোড (syntax tree), ডেটাবেসের index (পর্ব ৩০-এর B-tree), এমনকি পর্ব ০৭-এর recursion tree — সবই tree.

সংজ্ঞা — দুইভাবে

Recursive সংজ্ঞা (প্রোগ্রামারের প্রিয়): একটি tree হয় খালি, নয়তো একটি বিশেষ node — root — আর তার নিচে শূন্য বা একাধিক আলাদা আলাদা tree, যাদের বলে subtree. লক্ষ করুন, সংজ্ঞার ভেতরেই “tree” শব্দটি আছে: বড় tree ছোট tree দিয়ে তৈরি। এজন্যই tree-র প্রায় সব অ্যালগরিদম recursion দিয়ে দুই-তিন লাইনে লেখা যায় (পর্ব ০৭).

গ্রাফের সংজ্ঞা (গণিতবিদের প্রিয়, পর্ব ৩৯-এ বিস্তারিত): tree হলো এমন একটি graph যা connected (যেকোনো দুই node-এর মধ্যে পথ আছে) আর যাতে কোনো চক্র (cycle) নেই। দুই node-কে জোড়া রেখার নাম edge. যেকোনো একটি node-কে root বেছে “ঝুলিয়ে” দিলেই rooted tree পাওয়া যায় — আর এই পর্বের সব tree rooted.

২ · Tree-এর পরিভাষা — root থেকে leaf পর্যন্ত

Tree-র শব্দগুলো এসেছে দুই জায়গা থেকে: গাছ (root, leaf, branch) আর পরিবার (parent, child, sibling, ancestor). মজার ব্যাপার, কম্পিউটার বিজ্ঞানে গাছটি উল্টো আঁকা হয় — শিকড় ওপরে, পাতা নিচে। এই পর্ব জুড়ে নিচের tree-টি আমাদের সঙ্গী থাকবে:

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

নিচের ডায়াগ্রামে এই শব্দগুলো একে একে tree-র ওপর দেখুন। “পরে” চাপুন:

৩ · Binary tree আর তার প্রকারভেদ

সাধারণ tree-তে একটি node-এর যত খুশি সন্তান থাকতে পারে — একটি জেলায় যতগুলো উপজেলা। কিন্তু অ্যালগরিদমে সবচেয়ে বেশি ব্যবহৃত হয় binary tree: প্রতিটি node-এর সর্বোচ্চ দুটি সন্তান, আর তাদের নাম আলাদা — বাঁ সন্তান আর ডান সন্তান. “বাঁ” আর “ডান” এখানে শুধু ছবির ব্যাপার নয়, সংজ্ঞার অংশ: শুধু বাঁ সন্তানওয়ালা 1 → 2 আর শুধু ডান সন্তানওয়ালা 1 → 2 দুটি আলাদা binary tree. প্রধান উদাহরণের tree-টিও একটি binary tree; সেখানে 3-এর শুধু ডান সন্তান আছে।

   Full           Complete         Perfect          Degenerate
    o                o                o              o
   / \             /   \            /   \             \
  o   o           o     o          o     o             o
     / \         / \   /          / \   / \           /
    o   o       o   o o          o   o o   o         o
                                                      \
 (0 বা 2 সন্তান)  (শেষ level বাঁয়ে) (সব level ভরা)       o

প্রতিটি perfect tree একই সাথে full আর complete; কিন্তু উল্টোটা সত্য নয়। ওপরের “Full” ছবিটি complete নয় (level 1-এর বাঁ node-এর সন্তান নেই অথচ ডানের আছে), আর “Complete” ছবিটি full নয় (একটি node-এর একটিই সন্তান)। প্রধান উদাহরণের tree কোনোটিই নয়: 3-এর একটি সন্তান, তাই full নয়; level 2-এ 3-এর বাঁ ঘর ফাঁকা, তাই complete-ও নয়।

কতগুলো node, কত উচ্চতা — তিনটি প্রমাণ

(ক) level d-তে সর্বোচ্চ 2^d টি node. Induction (পর্ব ০৩): level 0-তে শুধু root, 2⁰ = 1. level d-তে সর্বোচ্চ 2^d টি থাকলে, প্রত্যেকের সর্বোচ্চ দুটি সন্তান, তাই level d + 1-এ সর্বোচ্চ 2 · 2^d = 2^d+1.

(খ) উচ্চতা h হলে মোট node সর্বোচ্চ 2^h+1 − 1. সব level যোগ করুন: 1 + 2 + 4 + … + 2^h = 2^h+1 − 1 (পর্ব ০৬-এর geometric series). সমতা হয় ঠিক তখন, যখন প্রতিটি level পুরো ভরা — অর্থাৎ perfect tree-তে। উচ্চতা 3-এর binary tree-তে তাই বড়জোর 15টি node; আমাদের উদাহরণে আছে ৮টি।

(গ) n টি node-এর binary tree-র উচ্চতা অন্তত ⌊log₂ n⌋. (খ) থেকে n ≤ 2^h+1 − 1, অর্থাৎ 2^h+1 ≥ n + 1, তাই h ≥ log₂(n + 1) − 1; h পূর্ণসংখ্যা বলে h ≥ ⌈log₂(n + 1)⌉ − 1, যা ঠিক ⌊log₂ n⌋-এর সমান। উদাহরণে n = 8: ⌊log₂ 8⌋ = 3 — আমাদের tree-র উচ্চতা ঠিক এই সর্বনিম্ন মানেই। আর সবচেয়ে বেশি উচ্চতা? degenerate tree-তে n − 1. অর্থাৎ একই n টি node-এ উচ্চতা log n থেকে n পর্যন্ত যেকোনো কিছু হতে পারে. দশ লাখ node-এ এটি ১৯ বনাম ৯,৯৯,৯৯৯ — পর্ব ২৭-এর BST কেন মাঝে মাঝে ধীর হয়ে যায়, আর পর্ব ২৮–২৯-এ কেন ভারসাম্য রাখার এত আয়োজন, তার মূল কারণ এটিই।

আরেকটি সুন্দর তথ্য: full binary tree-তে leaf-এর সংখ্যা = internal node-এর সংখ্যা + 1. I টি internal node থাকলে প্রত্যেকের ঠিক দুটি সন্তান, তাই edge = 2I. আবার edge = n − 1 = I + L − 1. দুটি মিলিয়ে 2I = I + L − 1, অর্থাৎ L = I + 1. ক্রিকেটের নকআউট টুর্নামেন্টে ১৬টি দল (leaf) থাকলে ম্যাচ (internal node) হয় ঠিক ১৫টি — প্রতিটি ম্যাচে একটি দল বাদ পড়ে, আর শেষে একটি দল টিকে থাকে।

৪ · Tree মেমরিতে রাখা — চারটি উপস্থাপন

কাগজে tree আঁকা সহজ; কিন্তু কম্পিউটারের মেমরি তো একটি লম্বা সারি (পর্ব ১০). সেই সারিতে “কে কার সন্তান” কীভাবে রাখবেন? চারটি প্রচলিত উপায় আছে, আর প্রতিটির শক্তি আলাদা।

(১) Linked node — প্রতিটি node-এ দুটি pointer

পর্ব ১২-এর linked list-এ প্রতিটি node-এ ছিল একটি next pointer; binary tree-তে থাকে দুটি — left আর right. সন্তান না থাকলে pointer খালি (nullptr বা None). দরকার হলে ওপরে ওঠার জন্য তৃতীয় একটি parent pointer-ও রাখা যায়।

struct Node {
    int val;
    Node* left  = nullptr;     // left child, or nullptr
    Node* right = nullptr;     // right child, or nullptr
    // Node* parent = nullptr; // optional: lets you walk upwards
};

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = Node(1, Node(2, Node(4), Node(5, Node(7), Node(8))), Node(3, None, Node(6)))

এটিই সবচেয়ে নমনীয়: যেকোনো আকারের tree, node যোগ-বাদ O(1)-এ (জায়গা জানা থাকলে). খরচ হলো প্রতি node-এ দুটি pointer (৬৪-বিট মেশিনে ১৬ byte) আর মেমরিতে ছড়িয়ে থাকা node — cache-এর জন্য খারাপ (পর্ব ১০, ১২). আর একটি মজার হিসাব: n টি node-এ মোট 2n টি pointer-ঘর, কিন্তু edge মাত্র n − 1 টি — তাই n + 1 টি pointer সবসময় খালি. এই অব্যবহৃত ঘরগুলো কাজে লাগানোর বুদ্ধি থেকেই এসেছে threaded tree আর Morris traversal (অংশ ৬).

(২) Array — heap-এর মতো index দিয়ে

পর্ব ২৩-এ দেখেছেন: complete binary tree-কে level ধরে বাঁ থেকে ডানে একটি array-তে রাখলে কোনো pointer লাগে না — 0-based index i-এর সন্তান 2i + 1 আর 2i + 2, parent (i − 1)/2. যেকোনো binary tree-ও এভাবে রাখা যায়, শুধু অনুপস্থিত node-এর ঘর খালি থাকে। আমাদের উদাহরণে 6 আছে 3-এর ডানে, তাই index 2·2 + 2 = 6; আর 7 আছে 5-এর (index 4) বাঁয়ে, তাই index 9:

index:  0  1  2  3  4  5  6  7  8  9  10
value:  1  2  3  4  5  -  6  -  -  7  8      (- = খালি ঘর)

১১টি ঘরে ৮টি node — চলে। কিন্তু degenerate tree-তে, যেখানে প্রতিটি node শুধু ডান সন্তান, depth d-এর node বসে index 2^d+1 − 2-এ; n টি node-এর জন্য array লাগে 2ⁿ − 1 ঘরের! তাই এই পদ্ধতি শুধু complete বা প্রায়-complete tree-র জন্য — heap, আর পর্ব ৩৪-এর segment tree.

(৩) Parent array — প্রত্যেকে শুধু তার parent-কে চেনে

node-গুলোর নম্বর 1 থেকে n হলে একটি array par[v] রাখুন — v-এর parent কে (root-এর জন্য 0 বা −1). উদাহরণে: par[2] = 1, par[3] = 1, par[4] = 2, par[5] = 2, par[6] = 3, par[7] = 5, par[8] = 5. মাত্র n টি সংখ্যা! ওপরে ওঠা O(1), তাই “এই উপজেলা অফিস কোন মন্ত্রণালয়ের অধীনে” জাতীয় প্রশ্নে চমৎকার — depth বের করা, দুই node-এর সাধারণ পূর্বপুরুষ খোঁজা (অংশ ৯), আর পর্ব ৩৩-এর union-find পুরোটাই এই উপস্থাপনে চলে। দুর্বলতা: কারও সন্তান কারা, জানতে পুরো array দেখতে হয় — O(n). আর বাঁ-ডানের পার্থক্যও এতে নেই।

(৪) Child list আর left-child right-sibling — যেকোনো সংখ্যক সন্তান

সাধারণ tree-তে (জেলার অধীনে যতগুলো উপজেলা) প্রতিটি node-এর জন্য তার সন্তানদের একটি list রাখুন: vector<int> children[v]. কনটেস্টে tree সাধারণত আসে n − 1 টি edge হিসেবে (“u আর v যুক্ত”); তখন প্রতিটি node-এর প্রতিবেশীদের list (adjacency list, পর্ব ৩৯) বানিয়ে root থেকে DFS করলেই parent আর সন্তান আলাদা হয়ে যায়।

আরেকটি চতুর উপায় left-child right-sibling: প্রতিটি node-এ মাত্র দুটি pointer — firstChild (প্রথম সন্তান) আর nextSibling (পরের ভাই/বোন)। মন্ত্রণালয়ের উদাহরণে অধিদপ্তরের firstChild রাজশাহী জেলা অফিস, আর রাজশাহীর nextSibling সিলেট। যেকোনো সংখ্যক সন্তানের tree এভাবে একটি binary tree হয়ে যায় — Donald Knuth-এর The Art of Computer Programming-এ এই রূপান্তরকে বলা হয়েছে tree আর binary tree-র “স্বাভাবিক সম্পর্ক”. ফাইল সিস্টেম আর পুরোনো অনেক কম্পাইলারের ভেতরে এই কাঠামো পাওয়া যায়।

৫ · Depth-first traversal — preorder, inorder, postorder

Array-তে সব উপাদান দেখার উপায় একটিই: বাঁ থেকে ডানে। Tree-তে কোনো স্বাভাবিক “বাঁ থেকে ডান” নেই — তাই প্রতিটি node ঠিক একবার দেখার (visit করার) নিয়মটি আমাদেরই ঠিক করতে হয়। এই কাজের নাম tree traversal. সবচেয়ে প্রচলিত তিনটি নিয়ম depth-first: একটি শাখা ধরে যতদূর যাওয়া যায় যাওয়া, তারপর ফিরে এসে পরের শাখা। তিনটির পার্থক্য শুধু একটি প্রশ্নে — root-কে কখন দেখবেন?

নামগুলো মনে রাখার কৌশল: “pre” মানে আগে, “in” মানে মাঝে, “post” মানে পরে — root-এর অবস্থান অনুযায়ী। আর বাঁ subtree সবসময় ডানের আগে। কোডে তিনটি প্রায় হুবহু এক; শুধু “visit” লাইনটি জায়গা বদলায়:

Pseudocode — recursive depth-first traversals (t = a node, NIL = empty)

preorder(t):    if t == NIL: return
                visit(t);  preorder(t.left);  preorder(t.right)

inorder(t):     if t == NIL: return
                inorder(t.left);  visit(t);  inorder(t.right)

postorder(t):   if t == NIL: return
                postorder(t.left);  postorder(t.right);  visit(t)

এই হাঁটা ঠিক recursion-এর ডাক আর ফেরা। নিচে একটি ছোট tree-তে (A-এর সন্তান B, C; B-এর সন্তান D, E) দেখুন কোন মুহূর্তে কোন ক্রমে কে যুক্ত হয়, আর call stack-এ তখন কে কে আছে:

বিশ্লেষণ. প্রতিটি node-এর জন্য ফাংশনটি ঠিক একবার ডাকা হয়, আর প্রতিটি খালি সন্তানের জন্যও একবার (সেই n + 1 টি nullptr) — মোট 2n + 1 টি ডাক, প্রতিটিতে O(1) কাজ। তাই সময় Θ(n). বাড়তি জায়গা হলো call stack-এর সর্বোচ্চ গভীরতা, যা height + 1 — অর্থাৎ O(h): ভারসাম্যপূর্ণ tree-তে O(log n), কিন্তু degenerate tree-তে Θ(n). শেষের কথাটি বাস্তবে গুরুত্বপূর্ণ — পরের অংশে দেখবেন কেন।

৬ · Recursion ছাড়া — explicit stack দিয়ে traversal

ধরুন একটি কনটেস্টের ইনপুটে ২,০০,০০০ node-এর tree, আর সেটি আসলে একটি লম্বা শিকল (degenerate). Recursive inorder-এ call stack ২,০০,০০০ frame গভীর হবে। Python-এ ডিফল্ট recursion limit মাত্র ১০০০ — RecursionError. C++-এ সিস্টেমের stack সীমিত (প্রায়ই কয়েক মেগাবাইট), তাই প্রোগ্রাম হঠাৎ crash করতে পারে — পর্ব ০৭-এর stack overflow. সমাধান: recursion যে stack লুকিয়ে ব্যবহার করত, সেটি নিজে হাতে রাখুন। নিজের stack থাকে heap memory-তে, যার সীমা অনেক বড়।

Iterative inorder-এর ধারণা: একটি pointer cur নিয়ে যতদূর সম্ভব বাঁয়ে নামুন, পথের প্রতিটি node stack-এ রাখুন (এরা “বাঁ subtree শেষ হওয়ার অপেক্ষায়”). বাঁয়ে আর যাওয়া না গেলে stack-এর ওপরেরটি তুলুন — তার বাঁ দিক শেষ, তাই এখন তাকে visit করুন — তারপর তার ডান সন্তানে গিয়ে আবার একই কাজ।

vector<int> inorderIter(Node* root) {
    vector<int> out; stack<Node*> st; Node* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }   // go left as far as possible
        cur = st.top(); st.pop();                         // its left side is finished
        out.push_back(cur->val);                          // visit
        cur = cur->right;                                 // now do its right subtree
    }
    return out;
}
vector<int> preorderIter(Node* root) {
    vector<int> out; stack<Node*> st;
    if (root) st.push(root);
    while (!st.empty()) {
        Node* u = st.top(); st.pop(); out.push_back(u->val);
        if (u->right) st.push(u->right);                 // right first, so left pops first
        if (u->left)  st.push(u->left);
    }
    return out;
}

def inorder_iter(root):
    out, st, cur = [], [], root
    while cur or st:
        while cur:                  # go left as far as possible
            st.append(cur); cur = cur.left
        cur = st.pop()              # its left side is finished
        out.append(cur.val)         # visit
        cur = cur.right             # now do its right subtree
    return out

def preorder_iter(root):
    out, st = [], [root] if root else []
    while st:
        u = st.pop(); out.append(u.val)
        if u.right: st.append(u.right)   # right first, so left pops first
        if u.left:  st.append(u.left)
    return out

প্রধান উদাহরণের tree-তে iterative inorder ধাপে ধাপে দেখুন:

কেন ঠিক কাজ করে — invariant. প্রতিবার বাইরের লুপের শুরুতে একটি কথা সত্য: “যা এখনো visit হয়নি, তার সঠিক inorder ক্রম হলো — আগে cur-এর পুরো subtree-র inorder, তারপর stack-এর ওপর থেকে নিচে প্রতিটি node u-এর জন্য: u নিজে, তারপর u-এর ডান subtree-র inorder.” শুরুতে cur = root আর stack খালি — সত্য। ভেতরের লুপ cur-এর বাঁ-পথ stack-এ তোলে, যা এই ক্রম বদলায় না (একটি node-এর inorder মানে বাঁ subtree, নিজে, ডান subtree). তারপর stack-এর ওপরের node-টিই ক্রমের প্রথম জন, তাই তাকে visit করা ঠিক, আর cur = তার ডান সন্তান করলে কথাটি আবার সত্য হয়। cur আর stack দুটোই খালি হলে বাকি কিছু নেই — সব ঠিক ক্রমে visit হয়েছে। প্রতিটি node ঠিক একবার push আর একবার pop হয় — সময় Θ(n), stack-এ সর্বোচ্চ h + 1 টি node — জায়গা O(h), recursion-এর সমান। পার্থক্য শুধু এই যে stack এখন আপনার নিয়ন্ত্রণে।

Iterative preorder আরও সহজ (ওপরের কোড): root push; তারপর বারবার pop করে visit, আর প্রথমে ডান সন্তান, পরে বাঁ সন্তান push — stack উল্টো ক্রমে বের করে বলে বাঁ আগে আসে। Iterative postorder-এর সবচেয়ে সহজ কৌশল: “root → ডান → বাঁ” ক্রমে একটি preorder চালান (preorderIter-এ দুই push-এর ক্রম বদলে), তারপর ফলটি উল্টে দিন — পাওয়া যায় “বাঁ → ডান → root”, অর্থাৎ postorder. এতে Θ(n) বাড়তি জায়গা লাগে; একটি stack আর “শেষে কাকে visit করেছি” pointer দিয়েও লেখা যায়, তবে কোডটি জটিল।

৭ · Level-order — queue দিয়ে স্তরে স্তরে

চতুর্থ traversal-টি অন্য রকম। সরকারি নির্দেশ যেভাবে ছড়ায় — প্রথমে মন্ত্রণালয়, তারপর সব অধিদপ্তর, তারপর সব জেলা অফিস, শেষে সব উপজেলা অফিস — সেভাবে tree পড়া: level 0, তারপর level 1-এর সবাই বাঁ থেকে ডানে, তারপর level 2. একে বলে level-order traversal, আর এটিই tree-তে breadth-first search (BFS, পর্ব ৪০-এ গ্রাফে বিস্তারিত)।

এখানে stack চলবে না, কারণ stack সবচেয়ে নতুনটিকে আগে দেয় — তাতে গভীরে নেমে যাওয়া হয়। দরকার “আগে এলে আগে” — পর্ব ১৪-এর queue. নিয়ম: root-কে queue-তে রাখুন; তারপর যতক্ষণ queue খালি নয়, সামনের node বের করে visit করুন আর তার সন্তানদের (বাঁ, তারপর ডান) পেছনে ঢোকান। টিকিটের লাইনের মতো: যে আগে লাইনে দাঁড়িয়েছে, তার কাজ আগে হয়; আর নতুন যারা এল, তারা লাইনের শেষে।

বিশ্লেষণ. প্রতিটি node একবার ঢোকে, একবার বের হয় — সময় Θ(n). জায়গা queue-র সর্বোচ্চ আকার, যা tree-র সবচেয়ে চওড়া level-এর কাছাকাছি — O(w), যেখানে w = সর্বোচ্চ চওড়া। এখানে DFS-এর সাথে একটি সুন্দর বৈপরীত্য: perfect tree-তে শেষ level-এ প্রায় n/2 টি node, তাই level-order-এর জায়গা Θ(n) কিন্তু DFS-এর মাত্র Θ(log n); আর degenerate tree-তে উল্টো — DFS-এর Θ(n), level-order-এর O(1). কোন traversal ব্যবহার করবেন, তা অনেক সময় tree-র আকৃতির ওপর নির্ভর করে।

Level আলাদা করে দরকার হলে (যেমন “প্রতিটি level আলাদা লাইনে ছাপুন” বা “প্রতিটি level-এর ডানের node”), লুপের শুরুতে queue-র আকার k মনে রাখুন আর ঠিক k টি node বের করুন — এই k টি-ই একটি পুরো level. অনুশীলন ৪-এ এটি লাগবে।

কোডে — চারটি traversal, height আর diameter একসাথে

এবার প্রধান উদাহরণের tree বানিয়ে চারটি traversal ছাপুন, আর সাথে height আর diameter (tree-র যেকোনো দুই node-এর মধ্যে সবচেয়ে লম্বা পথ, edge-এ মাপা) — অংশ ৯-এ diameter-এর যুক্তি বিস্তারিত। C++-এ node-গুলো একটি vector-এ রাখা হয়েছে, যাতে new/delete ছাড়াই pointer দিয়ে জোড়া যায়:

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
struct Node { int val = 0; Node* left = nullptr; Node* right = nullptr; };
using V = vector<int>;
void pre(Node* t, V& o)  { if (t) { o.push_back(t->val); pre(t->left, o); pre(t->right, o); } }
void in(Node* t, V& o)   { if (t) { in(t->left, o); o.push_back(t->val); in(t->right, o); } }
void post(Node* t, V& o) { if (t) { post(t->left, o); post(t->right, o); o.push_back(t->val); } }
V level(Node* t) {
    V o; queue<Node*> q; if (t) q.push(t);
    while (!q.empty()) {
        Node* u = q.front(); q.pop(); o.push_back(u->val);
        if (u->left) q.push(u->left);
        if (u->right) q.push(u->right);
    }
    return o;
}
pair<int, int> heightDiam(Node* t) {      // (height, diameter) in edges; empty tree = (-1, 0)
    if (!t) return {-1, 0};
    auto [hl, dl] = heightDiam(t->left); auto [hr, dr] = heightDiam(t->right);
    return {1 + max(hl, hr), max({dl, dr, hl + hr + 2})};   // hl + hr + 2 = longest path bending at t
}
void show(const char* name, const V& o) { cout << name; for (int x : o) cout << ' ' << x; cout << '\n'; }
int main() {
    vector<Node> pool(9);                 // pool[v] is the node that holds value v
    for (int v = 1; v <= 8; ++v) pool[v].val = v;
    auto link = [&](int p, int l, int r) { pool[p].left = l ? &pool[l] : nullptr; pool[p].right = r ? &pool[r] : nullptr; };
    link(1, 2, 3); link(2, 4, 5); link(3, 0, 6); link(5, 7, 8); Node* root = &pool[1];
    V a, b, c; pre(root, a); in(root, b); post(root, c);
    show("preorder: ", a); show("inorder:  ", b); show("postorder:", c); show("level:    ", level(root));
    auto [h, d] = heightDiam(root); cout << "height: " << h << "  diameter: " << d << '\n';
}

preorder:  1 2 4 5 7 8 3 6
inorder:   4 2 7 5 8 1 3 6
postorder: 4 7 8 5 2 6 3 1
level:     1 2 3 4 5 6 7 8
height: 3  diameter: 5

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def pre(t, o):
    if t: o.append(t.val); pre(t.left, o); pre(t.right, o)
def ino(t, o):
    if t: ino(t.left, o); o.append(t.val); ino(t.right, o)
def post(t, o):
    if t: post(t.left, o); post(t.right, o); o.append(t.val)
def level(t):
    o, q = [], deque([t] if t else [])
    while q:
        u = q.popleft(); o.append(u.val)
        if u.left: q.append(u.left)
        if u.right: q.append(u.right)
    return o
def height_diam(t):                      # (height, diameter) in edges; empty tree = (-1, 0)
    if t is None: return -1, 0
    hl, dl = height_diam(t.left)
    hr, dr = height_diam(t.right)
    return 1 + max(hl, hr), max(dl, dr, hl + hr + 2)   # hl + hr + 2 = longest path bending at t

root = Node(1, Node(2, Node(4), Node(5, Node(7), Node(8))), Node(3, None, Node(6)))
for name, f in [("preorder: ", pre), ("inorder:  ", ino), ("postorder:", post)]:
    o = []; f(root, o); print(name, *o)
print("level:    ", *level(root))
h, d = height_diam(root)
print(f"height: {h}  diameter: {d}")

preorder:  1 2 4 5 7 8 3 6
inorder:   4 2 7 5 8 1 3 6
postorder: 4 7 8 5 2 6 3 1
level:     1 2 3 4 5 6 7 8
height: 3  diameter: 5

৮ · Traversal থেকে tree ফেরত — preorder আর inorder

উল্টো প্রশ্ন: শুধু traversal-এর ফল দেওয়া আছে, tree-টি কী ছিল? একটি traversal একা যথেষ্ট নয়। Preorder 1 2 3 দিয়ে ঠিক পাঁচটি আলাদা আকারের tree হয় — 1-এর বাঁয়ে 2, তার বাঁয়ে 3; বা 1-এর দুই পাশে 2 আর 3; ইত্যাদি। কিন্তু preorder আর inorder একসাথে দিলে (সব মান আলাদা হলে) tree ঠিক একটিই। কৌশলটি দুটি পর্যবেক্ষণে:

• Preorder-এর প্রথম মানটি root — preorder root দিয়েই শুরু হয়।
• Inorder-এ root-এর বাঁয়ে যারা, তারা ঠিক বাঁ subtree; ডানে যারা, ডান subtree — অংশ ৫-এর ডায়াগ্রামে দেখেছেন, inorder-এ root বসে দুই গোষ্ঠীর মাঝখানে।

বাঁ subtree-তে k টি node থাকলে preorder-এ root-এর পরের k টি মান ঠিক বাঁ subtree-র preorder (কারণ preorder প্রথমে পুরো বাঁ subtree শেষ করে, তারপর ডানে যায়), আর বাকিগুলো ডান subtree-র preorder. দুই ভাগেই আবার একই সমস্যা, ছোট আকারে — recursion. প্রধান উদাহরণের দুই traversal থেকে tree ফেরত আনুন:

কেন tree ঠিক একটিই — induction-এ প্রমাণ. n-এর ওপর strong induction. n = 0 হলে খালি tree, একটিই। ধরুন n-এর চেয়ে কম node-এর যেকোনো (preorder, inorder) জোড়া থেকে tree অনন্য। n টি node-এর যেকোনো tree T, যার traversal দুটি দেওয়া জোড়া, তার root অবশ্যই preorder-এর প্রথম মান r — অন্য কিছু হতে পারে না। সব মান আলাদা বলে r inorder-এ ঠিক এক জায়গায়, তাই T-এর বাঁ subtree-র মানের সেট (r-এর বাঁয়ের সবাই) আর আকার k বাধ্যতামূলকভাবে নির্দিষ্ট। তাহলে বাঁ subtree-র preorder আর inorder-ও নির্দিষ্ট (preorder-এর পরের k টি, inorder-এর প্রথম k টি), আর ডানের-ও। দুটিই n-এর চেয়ে ছোট, তাই induction অনুযায়ী দুই subtree অনন্য — ফলে T-ও অনন্য। ∎

একই যুক্তিতে postorder + inorder-ও যথেষ্ট (postorder-এর শেষ মান root), আর level-order + inorder-ও। কিন্তু preorder + postorder যথেষ্ট নয়: 1-এর বাঁয়ে 2 আর 1-এর ডানে 2 — দুটি tree-রই preorder 1 2, postorder 2 1. একমাত্র সন্তান বাঁয়ে না ডানে, তা জানার উপায় নেই। (Full binary tree-তে একমাত্র সন্তান থাকে না, তাই সেখানে এই জোড়াও যথেষ্ট।) আর মান পুনরাবৃত্তি হলে preorder + inorder-ও ব্যর্থ হতে পারে: দুটি node-এর মান 1 হলে 1 1 preorder আর 1 1 inorder — বাঁ না ডান, বলা যায় না।

Serialize — null চিহ্ন দিলে একটি traversal-ই যথেষ্ট

একটি tree ফাইলে লিখে রাখা বা নেটওয়ার্কে পাঠানোর কাজকে বলে serialization; ফেরত আনাকে deserialization. Preorder + inorder দুটি পাঠানো ঝামেলার, আর মান আলাদা হওয়ার শর্ত লাগে। সহজ উপায়: preorder লিখুন, আর প্রতিটি খালি সন্তানের জায়গায় একটি চিহ্ন, যেমন #. প্রধান উদাহরণ হয়ে যায়:

1 2 4 # # 5 7 # # 8 # # 3 # 6 # #

৮টি মান আর ৯টি # (সেই n + 1 টি খালি pointer) — মোট 2n + 1 টি token. ফেরত আনা এক নিঃশ্বাসে: একটি token পড়ুন; # হলে খালি tree ফেরত দিন; নইলে সেই মান দিয়ে node বানান, তারপর recursion দিয়ে আগে বাঁ, পরে ডান subtree পড়ুন। #-গুলো বলে দেয় কোথায় একটি subtree শেষ, তাই এখানে মান পুনরাবৃত্তি হলেও কোনো সমস্যা নেই — দুই দিকেই সময় Θ(n).

নিচের প্রোগ্রাম preorder + inorder থেকে tree বানায়, তারপর নতুন tree-র traversal আবার বের করে মিলিয়ে দেখে, আর serialize করে:

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct Node { int val; Node* left; Node* right; };
vector<Node> pool;                        // node storage (reserved, so pointers stay valid)
unordered_map<int, int> pos; size_t nxt = 0;   // value -> inorder index; next unused preorder position
Node* build(const vector<int>& pre, int lo, int hi) {   // this subtree owns inorder[lo..hi]
    if (lo > hi) return nullptr;
    int v = pre[nxt++], m = pos[v];       // next preorder value is this subtree's root
    pool.push_back({v, nullptr, nullptr}); Node* t = &pool.back();
    t->left = build(pre, lo, m - 1);      // left first: it comes first in preorder
    t->right = build(pre, m + 1, hi); return t;
}
void walk(Node* t, int order, vector<int>& o) {         // order: 0 = pre, 1 = in, 2 = post
    if (!t) return;
    if (order == 0) o.push_back(t->val);
    walk(t->left, order, o);
    if (order == 1) o.push_back(t->val);
    walk(t->right, order, o);
    if (order == 2) o.push_back(t->val);
}
string serialize(Node* t) {               // preorder with '#' for every empty child
    return t ? to_string(t->val) + " " + serialize(t->left) + " " + serialize(t->right) : "#";
}
int main() {
    vector<int> pre{1, 2, 4, 5, 7, 8, 3, 6}, in{4, 2, 7, 5, 8, 1, 3, 6};
    for (int i = 0; i < (int)in.size(); ++i) pos[in[i]] = i;
    pool.reserve(pre.size()); Node* t = build(pre, 0, (int)in.size() - 1);
    vector<int> p, q, r; walk(t, 0, p); walk(t, 1, q); walk(t, 2, r);
    cout << "postorder:"; for (int x : r) cout << ' ' << x;
    cout << "\npreorder matches: " << (p == pre ? "yes" : "no") << "\ninorder matches:  " << (q == in ? "yes" : "no");
    cout << "\nserialized: " << serialize(t) << '\n';
}

postorder: 4 7 8 5 2 6 3 1
preorder matches: yes
inorder matches:  yes
serialized: 1 2 4 # # 5 7 # # 8 # # 3 # 6 # #

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build_tree(pre, ino):                # values must be distinct
    pos = {v: i for i, v in enumerate(ino)}
    nxt = iter(pre)                      # preorder is consumed left to right
    def build(lo, hi):                   # this subtree owns ino[lo..hi]
        if lo > hi: return None
        v = next(nxt); m = pos[v]        # next preorder value is this subtree's root
        left = build(lo, m - 1)          # build left first: it comes first in preorder
        return Node(v, left, build(m + 1, hi))
    return build(0, len(ino) - 1)

def walk(t, order, o):                   # order: 0 = pre, 1 = in, 2 = post
    if t is None: return o
    if order == 0: o.append(t.val)
    walk(t.left, order, o)
    if order == 1: o.append(t.val)
    walk(t.right, order, o)
    if order == 2: o.append(t.val)
    return o

def serialize(t):                        # preorder with '#' for every empty child
    return "#" if t is None else f"{t.val} {serialize(t.left)} {serialize(t.right)}"

pre = [1, 2, 4, 5, 7, 8, 3, 6]
ino = [4, 2, 7, 5, 8, 1, 3, 6]
t = build_tree(pre, ino)
print("postorder:", *walk(t, 2, []))
print("preorder matches:", "yes" if walk(t, 0, []) == pre else "no")
print("inorder matches: ", "yes" if walk(t, 1, []) == ino else "no")
print("serialized:", serialize(t))

postorder: 4 7 8 5 2 6 3 1
preorder matches: yes
inorder matches:  yes
serialized: 1 2 4 # # 5 7 # # 8 # # 3 # 6 # #

৯ · Tree-এর ক্লাসিক সমস্যা — একই ছাঁচ, ভিন্ন প্রশ্ন

Tree-র বেশিরভাগ ইন্টারভিউ সমস্যা একটি প্রশ্নে নামে: “দুই সন্তানের উত্তর জানা থাকলে নিজের উত্তর কীভাবে বানাব?” এটিই postorder-এর ছাঁচ, আর এর শুদ্ধতা প্রমাণ হয় structural induction-এ — খালি tree-তে ঠিক, আর দুই subtree-তে ঠিক হলে পুরোটায় ঠিক। প্রতিটি node-এ O(1) কাজ হলে সময় Θ(n), জায়গা O(h).

Diameter — বাঁক কোথায়, তা খুঁজুন

Tree-র যেকোনো সবচেয়ে লম্বা পথ কোথাও না কোথাও “সবচেয়ে উঁচু” একটি node-এ বাঁক নেয় — পথটি সেই node থেকে বাঁ subtree-তে নামে আর ডান subtree-তে নামে (একদিকে শূন্যও হতে পারে)। যে node t-তে বাঁক, সেখানে সবচেয়ে লম্বা সম্ভাব্য পথ = (বাঁ subtree-র height + 1) + (ডানের height + 1) = hl + hr + 2. তাই diameter = সব node-এ hl + hr + 2-এর সর্বোচ্চ। প্রতিটি node-এ height তো postorder-এ এমনিতেই বের হচ্ছে — একই হাঁটায় সর্বোচ্চটিও রাখা যায়। কোডের heightDiam ঠিক এটিই করে; নিচে নিচ থেকে ওপরে হিসাবটি দেখুন:

সাধারণ ভুল ১: “diameter = height(L) + height(R) + 2, শুধু root-এ” — সবচেয়ে লম্বা পথ root দিয়ে না-ও যেতে পারে (অনুশীলন ৩). সাধারণ ভুল ২: প্রতিটি node-এ আলাদা করে height() ডাকা — প্রতিটি ডাক O(n), তাই degenerate tree-তে মোট Θ(n²). একই postorder-এ দুটি মান একসাথে ফেরত দিলে Θ(n). পর্ব ৪৮-এ সাধারণ (binary নয় এমন) tree-তে দুইবার BFS/DFS দিয়ে diameter বের করার আরেকটি সুন্দর পদ্ধতি দেখবেন।

Symmetric কি না — আয়নার প্রশ্ন

একটি tree symmetric, যদি root-এর মাঝ দিয়ে একটি আয়না রাখলে বাঁ অর্ধেক ডান অর্ধেকের প্রতিবিম্ব হয়। প্রশ্নটি দুটি subtree-র ওপর: mirror(a, b) সত্য হয় যদি দুটিই খালি; অথবা দুটিই আছে, মান সমান, আর a-এর বাঁ b-এর ডানের আয়না এবং a-এর ডান b-এর বাঁয়ের আয়না। উত্তর = mirror(root.left, root.right). প্রতিটি node একবার তুলনা হয় — Θ(n). প্রধান উদাহরণ symmetric নয়: root-এর বাঁয়ে 2, ডানে 3 — মানই আলাদা।

Lowest common ancestor (LCA)

দুটি node p আর q-এর lowest common ancestor হলো সেই node, যে দুজনেরই ancestor (একজন নিজেও হতে পারে) আর যে root থেকে সবচেয়ে দূরে — বংশতালিকায় দুই চাচাতো ভাইয়ের “সবচেয়ে কাছের সাধারণ দাদা”. প্রধান উদাহরণে LCA(7, 4) = 2, LCA(7, 6) = 1, LCA(5, 8) = 5. Binary tree-তে একটি সরল recursive সমাধান:

// returns p, q, their LCA, or nullptr, depending on what this subtree contains
Node* lca(Node* t, Node* p, Node* q) {
    if (!t || t == p || t == q) return t;
    Node* L = lca(t->left, p, q);
    Node* R = lca(t->right, p, q);
    if (L && R) return t;          // p on one side, q on the other: t is the split point
    return L ? L : R;              // both (or the only one found) are on one side
}

যুক্তি: ফাংশনটি জানায় t-এর subtree-তে p বা q-এর কোনটি পাওয়া গেছে। দুই দিক থেকেই কিছু এলে p আর q দুই আলাদা subtree-তে — t-ই সেই প্রথম বিন্দু যেখানে তাদের পথ আলাদা হয়, তাই LCA. শুধু এক দিক থেকে এলে উত্তর সেদিকেই। (এখানে ধরে নেওয়া হয়েছে p আর q দুজনেই tree-তে আছে।) প্রতিটি প্রশ্নে O(n). Parent array থাকলে আরেক উপায়: দুজনের depth সমান করে একসাথে ওপরে উঠুন — O(h). লাখো প্রশ্ন থাকলে পর্ব ৪৮-এর binary lifting O(n log n) প্রস্তুতির পর প্রতিটি প্রশ্নে O(log n) দেয়।

Expression tree — postfix-এর গোপন রূপ

গণিতের রাশি (3 + 4) * (5 - 2) একটি expression tree: প্রতিটি internal node একটি operator, প্রতিটি leaf একটি সংখ্যা — আর এটি একটি full binary tree. বন্ধনীর আর দরকার নেই, কারণ গঠনই বলে দেয় কী আগে হবে।

          *
        /   \
      +       -
     / \     / \
    3   4   5   2

preorder  : * + 3 4 - 5 2      (prefix, Polish notation)
inorder   : 3 + 4 * 5 - 2      (বন্ধনী হারিয়ে গেছে — অর্থ বদলে যায়!)
postorder : 3 4 + 5 2 - *      (postfix — পর্ব ১৩-এর stack-এ মান বের করা যায়)

লক্ষ করুন: postorder হুবহু পর্ব ১৩-এর postfix রূপ। Tree-র মান বের করাও একটি postorder: দুই সন্তানের মান আগে, তারপর operator প্রয়োগ — (3 + 4) = 7, (5 − 2) = 3, 7 × 3 = 21. আর উল্টো দিকে, postfix থেকে tree বানানো যায় পর্ব ১৩-এর stack দিয়েই: সংখ্যা পেলে একটি leaf push; operator পেলে দুটি pop (প্রথমটি ডান, দ্বিতীয়টি বাঁ সন্তান), নতুন node বানিয়ে push. শেষে stack-এ একটিই node — root. Inorder থেকে সঠিক রাশি পেতে প্রতিটি operator-এর subtree-কে বন্ধনীতে মুড়তে হয়: ((3 + 4) * (5 - 2)). কম্পাইলার ঠিক এভাবে আপনার কোডকে একটি syntax tree বানায়, আর postorder ধরে মেশিনের নির্দেশ তৈরি করে।

১০ · AI-এর যুগে tree — কোড ছোট, ভুল সূক্ষ্ম

Tree-র কোড সাধারণত পাঁচ-দশ লাইনের, আর AI এগুলো নির্ভুল দেখতে লেখে। কিন্তু ভুল লুকিয়ে থাকে সংজ্ঞায় (height edge-এ না node-এ?), ছোট পরীক্ষায় ধরা পড়ে না এমন জায়গায় (diameter root দিয়ে যায় না), আর বড় ইনপুটে (১,০০,০০০ গভীরতার শিকলে recursion ভেঙে পড়ে)। AI প্রায়ই আত্মবিশ্বাসের সাথে বলে “preorder + postorder থেকে tree অনন্য”, বা প্রতিটি node-এ height() ডেকে O(n²) সমাধানকে O(n) বলে দেয়।

Tree-র কোডে AI সাধারণত যেসব ভুল করে

Tree-র কোড যাচাইয়ের চেকলিস্ট

• height/depth/diameter edge-এ না node-এ, প্রশ্ন থেকে ঠিক করেছি আর খালি tree-র মান (−1 বা 0) সেই অনুযায়ী রেখেছি
• Edge case চালিয়েছি: খালি tree, এক node, শুধু বাঁ-শিকল, শুধু ডান-শিকল, perfect tree
• প্রধান উদাহরণের মতো একটি ছোট tree-তে চারটি traversal আগে হাতে লিখে তারপর প্রোগ্রামের সাথে মিলিয়েছি
• এলোমেলো tree বানিয়ে আমার দ্রুত সমাধানকে একটি সরল brute force-এর সাথে (যেমন সব জোড়া node-এর দূরত্ব থেকে diameter) মিলিয়ে stress testing করেছি
• Tree ফেরত আনার পর তার traversal আবার বের করে ইনপুটের সাথে মিলিয়েছি (round-trip পরীক্ষা)
• গভীর tree-তে recursion depth-এর সীমা ভেবেছি — দরকার হলে iterative রূপ লিখেছি