Tree: গঠন দেখে সঠিক traversal বেছে নেওয়া

অধ্যায়ের সূচি · অনুশীলন ও সমাধান · মূল ধারণা

একটি tree-তে তথ্যের সঙ্গে কে কার নিচে আছে সেটিও রাখা হয়। Folder-এর মোট আকার জানতে তার ভেতরের সব file ও subfolder-এর আকার লাগে। আবার folder-এর পূর্ণ path বানাতে আগে parent-এর path জানতে হয়। একই tree, কিন্তু কাজের ক্রম আলাদা। এই পার্থক্য বুঝলেই traversal মুখস্থ করার প্রয়োজন কমে যায়।

কোন ক্রমে পড়বেন

ধাপ	পড়া	পড়ে কী করতে পারবেন
1	Node, edge, depth, height	একটি node-এর depth ও height আলাদা করে গুনতে
2	Traversal-এর সম্পূর্ণ ছবি	preorder, inorder, postorder ও level order হাতে লিখতে
3	Traversal বাছার নিয়ম	প্রশ্ন দেখে parent আগে লাগবে, না child আগে লাগবে বুঝতে
4	চলমান Python উদাহরণ	খালি tree, এক node ও একদিকে ঝুঁকে থাকা tree পরীক্ষা করতে
5	অনুশীলনের তালিকা	মূল প্রশ্ন ও ব্যাখ্যা পাশাপাশি খুলে সমাধান করতে

একটি প্রোগ্রাম: folder-এর মোট আকার

ধরি file-এর আকার নিচের ছবিতে দেওয়া আছে। Folder নিজের জন্য আলাদা আকার যোগ করবে না; শুধু children-এর মোট ফেরত দেবে।

flowchart TD
  root["project / মোট 14 KB"] --> src["src / মোট 9 KB"]
  root --> readme["README.md / 5 KB"]
  src --> main["main.py / 6 KB"]
  src --> helper["helper.py / 3 KB"]

শেষ হওয়া কাজ	কী জানা গেল	পরের ধাপ
main.py পড়া	6 KB	src-এর অন্য child দেখুন
helper.py পড়া	3 KB	src = 6 + 3 = 9 KB
src ফেরত এলো	9 KB	project-এর README পড়ুন
README.md পড়া	5 KB	project = 9 + 5 = 14 KB

এটি postorder: children-এর উত্তর পাওয়ার পরে parent-এর উত্তর। File system-এর বাস্তব symlink cycle তৈরি করতে পারে; এই উদাহরণে symlink অনুসরণ করা হচ্ছে না।

Python

def total_size(node):
    if "size" in node:        # file
        return node["size"]
    return sum(total_size(child) for child in node["children"])

project = {"children": [
    {"children": [{"size": 6}, {"size": 3}]},
    {"size": 5},
]}
assert total_size(project) == 14

প্রতিটি node একবার দেখা হয়, তাই সময় O(n)। Recursion stack-এ একসঙ্গে একটি root-to-leaf path থাকে, তাই অতিরিক্ত space O(h); chain হলে h বেড়ে n হতে পারে।

প্রশ্ন থেকে traversal

প্রোগ্রামের কাজ	কী আগে দরকার	পছন্দ
Menu-র প্রতিটি item-এর পূর্ণ path	Parent-এর path	Preorder; path নিচে পাঠান
Folder-এর মোট size বা expression-এর value	Children-এর উত্তর	Postorder; উত্তর উপরে ফেরান
Organization chart-এর প্রতি স্তরের মানুষ	একই depth-এর সব node	Queue দিয়ে level order
BST থেকে ascending report	ছোট → বর্তমান → বড়	Inorder
সাধারণ binary tree থেকে ascending report	BST ordering নেই	Values সংগ্রহ করে sort; শুধু inorder যথেষ্ট নয়

একটি শর্ত পুরো subtree-তে প্রযোজ্য

flowchart TD
  a["8"] --> b["3"]
  a --> c["10"]
  b --> d["1"]
  b --> e["9: ভুল অবস্থান"]

9 > 3 হওয়ায় parent-child তুলনা ঠিক মনে হচ্ছে। কিন্তু 9 রয়েছে 8-এর বাঁ subtree-তে, যেখানে সব value 8-এর ছোট হতে হবে। তাই validation-এ (low, high) সীমা নিচে পাঠাতে হয়। Validate BST-এর নোট খোলার আগে নিজে বলুন: 9-এর জন্য সীমা কত? উত্তর (3, 8)।

পরের ধাপে পূর্ণ অনুশীলন তালিকা থেকে traversal, depth, validation এবং LCA ক্রমে নিন। একটি traversal-এর output দেখে সাধারণ tree-এর গঠন সবসময় ফেরত পাওয়া যায় না; serialization-এ missing child-এর marker দরকার।