একটি বাইনারি ট্রি যেটির সর্বোচ্চ দুটি চাইল্ড থাকে, যাদের বাম চাইল্ড ও ডান চাইল্ড বলে নির্দিষ্ট করা হয়। এটি বাইনারি ট্রিতে সবচেয়ে গভীর বাম পাতা বের করার একটি C++ প্রোগ্রাম।
অ্যালগরিদম
শুরু. deepestLLeafutil() ফাংশন দেয়া বাইনারি ট্রিতে সবচেয়ে গভীর বাম পাতা বের করতে: lvel হলো করেন্ট নোডের লেভেল। maxlvel হলো এখন পর্যন্ত পাওয়া গভীরতম বাম পাতা নোডের পয়েন্টার। isLeft ইঙ্গিত দেয় যে এই নোডটি এর পেরেন্টের বাম চাইল্ড। resPtr হলো রেজাল্টের পয়েন্টার। যদি root NULL-এর সমান হয় তবে রিটার্ন করুন। রেজাল্ট আপডেট করুন যদি এই নোডটি বাম পাতা হয় এবং এর লেভেল বর্তমান রেজাল্টের ম্যাক্স লেভেল থেকে বেশি হয়। বাম ও ডান সাবট্রি জন্য deepestLLeafutil() ফাংশন রিকার্সিভলি কল করুন। শেষ।
উদাহরণ কোড
#include <iostream> using namespace std; struct n { int v; n *l, *r; }; void deepestLLeafutil(n *root, int lvel, int *maxvel, bool isLeft, n **resPtr) { if (root == NULL) return; if (isLeft && !root->l && !root->r && lvel > *maxvel) { *resPtr = root; *maxvel = lvel; return; } deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr); deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr); } n* deepestLLeaf( n *root) { int maxlevel = 0; n *res = NULL; deepestLLeafutil(root, 0, &maxlevel, false, &res); return res; } n *newnode(int d) { n *t = new n; t->v = d; t->l = t->r = NULL; return t; } int main() { n* root = newnode(9); root->l = newnode(7); root->r = newnode(10); root->l->l = newnode(6); root->r->l = newnode(8); root->r->r = newnode(19); root->r->l->r = newnode(4); root->r->r->r = newnode(20); n *res = deepestLLeaf(root); if (res) cout << "সবচেয়ে গভীর বাম পাতাটি হল " << res->v; else cout << "দেয়া ট্রিতে কোনো বাম পাতা নেই"; return 0; }আউটপুট
সবচেয়ে গভীর বাম পাতাটি হল 6
