Binary Trees ও BST

গল্পে বুঝি

ফাতিমা আল-ফিহরি আর তার ছোট ভাই আল-খোয়ারিজমি একটা খেলা খেলছে — “নাম্বার গেস করো”। ফাতিমা আল-ফিহরি মনে মনে ১ থেকে ১০০০-এর মধ্যে একটা সংখ্যা ঠিক করে রাখে, আল-খোয়ারিজমিকে সেটা খুঁজে বের করতে হবে। আল-খোয়ারিজমি যদি এক এক করে ১, ২, ৩ বলে যেত, তাহলে খারাপ সময়ে ১০০০ বার বলতে হতো। কিন্তু আল-খোয়ারিজমি চালাক — সে প্রথমে বলে “৫০০?”। ফাতিমা আল-ফিহরি বলে “বড়”। আল-খোয়ারিজমি সাথে সাথে বুঝে যায় নিচের ৫০০টা সংখ্যা বাদ, উত্তরটা ৫০১ থেকে ১০০০-এর মধ্যে। এবার সে বলে “৭৫০?” — ফাতিমা আল-ফিহরি বলে “ছোট”। প্রতিটা প্রশ্নে বাকি সম্ভাবনার অর্ধেক কেটে যাচ্ছে।

ঠিক এভাবেই একটা মোটা ছাপা অভিধানে শব্দ খুঁজি — মাঝখানে খুলি, যে শব্দ খুঁজছি সেটা এই পাতার আগে না পরে দেখি, তারপর বাঁ দিকের অর্ধেক বা ডান দিকের অর্ধেক নিয়ে আবার মাঝখানে খুলি। হাজার পাতার অভিধানেও দশ-বারো বার পাতা উল্টেই কাঙ্ক্ষিত শব্দে পৌঁছে যাই, প্রতিটা পাতা এক এক করে দেখতে হয় না। ফাতিমা আল-ফিহরির নাম্বারটা ধরো tree-র root node, তার ছোট মানগুলো এক পাশে, বড় মানগুলো আরেক পাশে — অনেকটা পরিবারের বংশতালিকার মতো, প্রতিটা parent-এর নিচে দুটো করে child।

এই “মাঝখানে গিয়ে ছোট হলে বাঁয়ে, বড় হলে ডানে” যাওয়াটাই binary search tree-র মূল কথা। প্রতিটা node-এর একটা মান থাকে, তার left subtree-র সব মান ছোট আর right subtree-র সব মান বড়। খুঁজতে গিয়ে প্রতি ধাপে একটা তুলনা করে অর্ধেক বাদ দিই, তাই n-টা মানের মধ্যেও মাত্র O(log n) ধাপে target পাওয়া যায় — সব node এক এক করে দেখতে হয় না। বাস্তবে database index ঠিক এই কাঠামোতেই লক্ষ লক্ষ row-র মধ্যে চোখের পলকে একটা রেকর্ড খুঁজে বের করে; যেকোনো দ্রুত lookup-এর পেছনে এই left-right halving-এর জাদু কাজ করে।

Tree কেন?

Tree hierarchical সম্পর্ক প্রকাশ করে: file system, DOM element, organization chart, database index। Binary tree — যেখানে প্রতিটি node-এর সর্বোচ্চ দুটি child থাকে — সবচেয়ে সাধারণ ধরন এবং heap, trie ও balanced search tree-র ভিত্তি।

Binary Tree-র মূল কথা

class TreeNode {
	val: number;
	left: TreeNode | null = null;
	right: TreeNode | null = null;

	constructor(val: number) {
		this.val = val;
	}
}

Tree Traversal

প্রতিটি node ভিজিট করার চারটি উপায় আছে। বিভিন্ন সমস্যার জন্য order-টা গুরুত্বপূর্ণ।

// In-order: left → root → right (gives sorted order for BST)
function inorder(root: TreeNode | null): number[] {
	if (!root) return [];
	return [...inorder(root.left), root.val, ...inorder(root.right)];
}

// Pre-order: root → left → right (copy/serialize a tree)
function preorder(root: TreeNode | null): number[] {
	if (!root) return [];
	return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

// Post-order: left → right → root (delete a tree, evaluate expressions)
function postorder(root: TreeNode | null): number[] {
	if (!root) return [];
	return [...postorder(root.left), ...postorder(root.right), root.val];
}

// Level-order: BFS — see each "row" of the tree
function levelOrder(root: TreeNode | null): number[][] {
	if (!root) return [];
	const result: number[][] = [];
	const queue: TreeNode[] = [root];

	while (queue.length) {
		const level: number[] = [];
		const size = queue.length;
		for (let i = 0; i < size; i++) {
			const node = queue.shift()!;
			level.push(node.val);
			if (node.left) queue.push(node.left);
			if (node.right) queue.push(node.right);
		}
		result.push(level);
	}
	return result;
}

সাধারণ Tree সমস্যা

Max Depth

function maxDepth(root: TreeNode | null): number {
	if (!root) return 0;
	return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Binary Tree Invert করা

function invertTree(root: TreeNode | null): TreeNode | null {
	if (!root) return null;
	[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
	return root;
}

Lowest Common Ancestor

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
	if (!root || root === p || root === q) return root;

	const left = lowestCommonAncestor(root.left, p, q);
	const right = lowestCommonAncestor(root.right, p, q);

	if (left && right) return root; // p and q are on different sides
	return left || right;
}

Binary Search Tree

একটা BST এই invariant বজায় রাখে: left child < parent < right child। এতে search, insert ও delete-এ O(log n) পাওয়া যায় — যদি tree-টা balanced থাকে।

class BST {
	root: TreeNode | null = null;

	insert(val: number): void {
		this.root = this._insert(this.root, val);
	}

	private _insert(node: TreeNode | null, val: number): TreeNode {
		if (!node) return new TreeNode(val);
		if (val < node.val) node.left = this._insert(node.left, val);
		else node.right = this._insert(node.right, val);
		return node;
	}

	search(val: number): boolean {
		let current = this.root;
		while (current) {
			if (val === current.val) return true;
			current = val < current.val ? current.left : current.right;
		}
		return false;
	}
}

মূল শিক্ষা

1. Recursively চিন্তা করুন — tree স্বভাবতই recursive structure
2. চারটি traversal-ই জানুন এবং কখন কোনটা ব্যবহার করবেন
3. BST O(log n) operation দেয় কিন্তু unbalanced হলে O(n)-এ নেমে যায়
4. DFS (pre/in/post-order) stack ব্যবহার করে; BFS (level-order) queue ব্যবহার করে