একটি স্পেশাল বাইনারি ট্রি দেওয়া আছে যার লীফ নোডগুলো সার্কুলার ডাবলি লিঙ্কড লিস্ট (circular doubly linked list) বানাতে কানেক্টেড। আমাদের এর হাইট (height) বের করতে হবে। বামপাশের সবচেয়ে বামের লীফের লেফ্ট পয়েন্টার (left pointer) সার্কুলার ডাবলি লিঙ্কড লিস্টের প্রিভিয়াস (previous) পয়েন্টার হিসেবে কাজ করবে, এবং এর রাইট পয়েন্টার (right pointer) নেক্সট (next) পয়েন্টার হিসেবে কাজ করবে।
এই কেসে হাইট বের করার 스트্যাটেজি (strategy) নরমাল বাইনারি সার্চ ট্রির মত। রিকার্সিভলি (recursively) একটি নোডের বাম ও ডান সাবট্রির হাইট ক্যালকুলেট করব এবং নোডের হাইট হবে দুটি চাইল্ডের ম্যাক্সিমাম + ১। কিন্তু এখানে লীফ নোডগুলো সার্কুলার ডাবলি লিঙ্কড লিস্টের এলিমেন্ট। তাই একটি নোড লীফ নোড কিনা চেক করতে হবে: নোডের left-এর right যদি নোডকে পয়েন্ট করে এবং right-এর left যদি নোডকে পয়েন্ট করে, তবে সেটি লীফ নোড।
উদাহরণ
#include<iostream> using namespace std; class Node { public: int data; Node *left, *right; }; bool isLeafNode(Node* node) { return node->left && node->left->right == node && node->right && node->right->left == node; } int findHeight(Node* node) { if (node == NULL) return 0; if (isLeafNode(node)) return 1; return 1 + max(findHeight(node->left), findHeight(node->right)); } Node* getNode(int data) { Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; return node; } int main() { Node* root = getNode(1); root->left = getNode(2); root->right = getNode(3); root->left->left = getNode(4); root->left->right = getNode(5); root->left->left->left = getNode(6); Node *L1 = root->left->left->left; Node *L2 = root->left->right; Node *L3 = root->right; L1->right = L2, L2->right = L3, L3->right = L1; L3->left = L2, L2->left = L1, L1->left = L3; cout << "Height of tree is: " << findHeight(root); }আউটপুট
Height of tree is: 4
