Binary tree ও BST: traversal ও interview প্যাটার্ন

Tree হলো node-এর শ্রেণিক্রম। Binary tree-এ প্রতিটি node-এর সর্বোচ্চ দুটি সন্তান (বাম ও ডান)। উপরের node root, সন্তানহীন node leaf, আর উচ্চতা হলো root থেকে leaf পর্যন্ত দীর্ঘতম পথ।

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }

Binary search tree (BST)

BST একটি ক্রম নিয়ম যোগ করে: প্রতিটি node-এর জন্য বাম subtree-র মান ছোট এবং ডান subtree-র মান বড়।

• খোঁজা, যোগ ও মোছা O(h) লাগে, h হলো উচ্চতা।
• Tree balanced হলে h প্রায় log n, তাই ক্রিয়া O(log n)।
• ভীষণ অসমতল হলে (যেমন sorted মান যোগ করলে) এটি list-এ নেমে O(n) হয়। Self-balancing tree (AVL, red-black) এটি ঠেকায়।
• BST-র inorder traversal মান sorted ক্রমে দেখে। এই তথ্য অনেক সমস্যা মেটায়।

চার traversal

Depth-first (DFS), node কখন দেখেন তার ওপর তিন ক্রম:

function preorder(n)  { if (!n) return; visit(n); preorder(n.left);  preorder(n.right); }  // node, left, right
function inorder(n)   { if (!n) return; inorder(n.left);  visit(n);  inorder(n.right); }   // left, node, right
function postorder(n) { if (!n) return; postorder(n.left); postorder(n.right); visit(n); } // left, right, node

• Preorder: tree কপি বা serialise (সন্তানের আগে parent)।
• Inorder: BST-তে sorted ক্রম।
• Postorder: নিচ থেকে উপরে হিসাব (parent-এর আগে সন্তান), যেমন উচ্চতা বা tree মোছা।

Breadth-first (BFS), level order, queue দিয়ে:

function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const size = queue.length, level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();       // বড় tree-তে আসল queue ব্যবহার করুন
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}
// সময় O(n), space O(প্রস্থ)

সব traversal প্রতিটি node একবার দেখে: O(n) সময়। DFS recursion O(h) stack জায়গা নেয়।

Tree-তে recursive ভাবনা

বেশিরভাগ tree সমস্যা এই প্যাটার্ন ব্যবহার করে: বামের সমাধান, ডানের সমাধান, node-এ মিলান, null-এর জন্য base case সহ।

উচ্চতা:

const height = (n) => (n ? 1 + Math.max(height(n.left), height(n.right)) : 0);

Same tree, invert tree, symmetric tree, path sum: সবই একই আকৃতির।

Diameter (দুটি node-এর মধ্যে দীর্ঘতম পথ): প্রতিটি node-এ তার মধ্য দিয়ে পথ হলো বাম উচ্চতা যোগ ডান উচ্চতা। উচ্চতা হিসাবের সময় সেরা মান ট্র্যাক করুন, এক পাসে।

Lowest common ancestor (LCA):

• সাধারণ binary tree-তে: বর্তমান node লক্ষ্যগুলোর একটি হলে তাকেই ফেরত দিন। দুই দিকে recurse করুন। দুই দিকই node ফেরত দিলে বর্তমান node-ই LCA।
• BST-তে: ক্রম ব্যবহার করুন। দুটি লক্ষ্যই ছোট হলে বামে যান। দুটিই বড় হলে ডানে। নইলে বর্তমান node-ই LCA।

BST যাচাই (একটি ক্লাসিক ফাঁদ)

শুধু প্রতিটি node তার বাম সন্তানের চেয়ে বড় ও ডান সন্তানের চেয়ে ছোট কি না দেখা ভুল। বাম subtree-র গভীরের একটি মান কোনো পূর্বপুরুষের চেয়ে বড় হতে পারে। বৈধ পরিসর নিচে পাঠান:

function isValidBST(node, lo = -Infinity, hi = Infinity) {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  return isValidBST(node.left, lo, node.val) && isValidBST(node.right, node.val, hi);
}

বিকল্পে, inorder traversal করে মান কঠোরভাবে বাড়ছে কি না দেখুন।

অন্যান্য প্যাটার্ন

• BST-তে k-তম ক্ষুদ্রতম: inorder traversal, k-তে থামুন।
• Preorder ও inorder array থেকে tree বানানো: preorder-এর প্রথম মান root; inorder-এ তাকে খুঁজে বাম ও ডান ভাগ করুন।
• Tree serialise ও deserialise: null চিহ্নসহ preorder।
• Binary tree-র ডান পাশের দৃশ্য: BFS-এর প্রতি স্তরের শেষ node।
• Trie, heap ও segment tree কঠিন সমস্যায় আসা অন্যান্য tree-আকৃতির structure।

Complexity ও space

• সময় সাধারণত O(n), কারণ প্রতিটি node একবার দেখা হয়।
• Space DFS recursion-এ O(h) (balanced-এ O(log n), সবচেয়ে খারাপে O(n)) এবং BFS-এ O(w), w হলো সর্বোচ্চ প্রস্থ।
• বাঁকা tree recursion খুব গভীর করতে পারে। গভীরতা বিশাল হতে পারলে স্পষ্ট stack-সহ iterative পদ্ধতি উল্লেখ করুন।

সাধারণ ভুল

• Null base case ভুলে যাওয়া।
• BST-কে সাধারণ binary tree-র সাথে গুলিয়ে যেখানে ক্রম নেই সেখানে ক্রম ব্যবহার।
• ওপরের BST যাচাই ফাঁদ।
• Recursion-এ ভাগ করা list বদলানো (সংরক্ষণের আগে path কপি করুন)।
• বড় array-তে shift() queue হিসেবে ব্যবহার, যা ধীর।

অনুশীলনের সমস্যা

Maximum Depth, Invert Binary Tree, Same Tree, Symmetric Tree, Level Order Traversal, Validate BST, Lowest Common Ancestor, Kth Smallest in BST, Diameter of Binary Tree, Construct Tree from Preorder and Inorder।

মূল কথা: চার traversal জানুন, null base case-সহ "বাম, ডান, মিলান" ভাবুন, BST-র sorted-inorder ধর্ম ব্যবহার করুন এবং পরিসর দিয়ে BST যাচাই করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ২ (data structure ও আচরণ): 2 নম্বর (মোট 5)। আগের লেখা: Linked list, stack ও queue: interview-এর প্যাটার্ন.