C++-এ BST-এর মেডিয়ান O(n) টাইম ও O(1) স্পেসে (মরিস ট্রাভার্সাল)

একটি বাইনারি সার্চ ট্রি (BST) দেওয়া আছে। এর মেডিয়ান বের করতে হবে। নোড সংখ্যা বিজোড় হলে মিডেল নোড, জোড় হলে দুটি মিডেল নোডের গড়। O(1) এক্সট্রা স্পেসে মরিস ইনঅর্ডার ট্রাভার্সাল ব্যবহার করা হয়।

উদাহরণ

BST (বিজোড় নোড):       7
                       / \
                      4   9
                     / \ / \
                    2 5 8 10
ইনঅর্ডার: 2,4,5,7,8,9,10 → মেডিয়ান = 7

BST (জোড় নোড):         7
                       / \
                      4   9
                     / \  /
                    2  5 8
ইনঅর্ডার: 2,4,5,7,8,9 → মেডিয়ান = (5+7)/2 = 6

মরিস ইনঅর্ডার ট্রাভার্সাল

• করেন্ট = রুট।
• যদি বাম চাইল্ড নেই: ভিজিট করুন, ডানে যান।
• বাম চাইল্ড থাকলে: ইনঅর্ডার প্রিডিসেসর খুঁজুন (বাম সাবট্রির রাইটমোস্ট)। তার রাইট চাইল্ড কে করেন্ট করুন, করেন্টকে বামে নিন।
• যদি প্রিডিসেসরের রাইট ইতিমধ্যে করেন্ট হয়: সেটি NULL করুন, ভিজিট করুন, ডানে যান।

অ্যালগরিদম

1. মরিস ট্রাভার্সাল দিয়ে টোটাল নোড কাউন্ট করুন (count)।
2. আবার মরিস ট্রাভার্সাল করুন, কাউন্ট রানিং রেখে মেডিয়ান পজিশনে পৌঁছালে ভ্যালু রিটার্ন করুন।
3. জোড় কেসের জন্য প্রিভিয়াস নোড রাখুন।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int item) {
    Node* t = new Node();
    t->data = item; t->left = t->right = NULL;
    return t;
}

Node* insert(Node* node, int key) {
    if (!node) return newNode(key);
    if (key < node->data) node->left = insert(node->left, key);
    else if (key > node->data) node->right = insert(node->right, key);
    return node;
}

int countNodes(Node* root) {
    Node *cur=root, *pre; int cnt=0;
    while (cur) {
        if (!cur->left) { cnt++; cur=cur->right; }
        else {
            pre = cur->left;
            while (pre->right && pre->right!=cur) pre=pre->right;
            if (!pre->right) { pre->right=cur; cur=cur->left; }
            else { pre->right=NULL; cnt++; cur=cur->right; }
        }
    }
    return cnt;
}

int findMedian(Node* root) {
    if (!root) return 0;
    int count = countNodes(root);
    int currCount = 0;
    Node *cur=root, *pre, *prev=NULL;

    while (cur) {
        if (!cur->left) {
            currCount++;
            if (count%2 && currCount==(count+1)/2) return cur->data;
            if (count%2==0 && currCount==count/2+1) return (prev->data + cur->data)/2;
            prev = cur;
            cur = cur->right;
        } else {
            pre = cur->left;
            while (pre->right && pre->right!=cur) pre=pre->right;
            if (!pre->right) { pre->right=cur; cur=cur->left; }
            else {
                pre->right=NULL;
                prev = pre;
                currCount++;
                if (count%2 && currCount==(count+1)/2) return cur->data;
                if (count%2==0 && currCount==count/2+1) return (prev->data + cur->data)/2;
                prev = cur;
                cur = cur->right;
            }
        }
    }
    return 0;
}

int main() {
    Node* root1 = NULL;
    root1 = insert(root1,7); insert(root1,4); insert(root1,2);
    insert(root1,5); insert(root1,9); insert(root1,8); insert(root1,10);
    cout << "Median (odd): " << findMedian(root1) << endl;

    Node* root2 = NULL;
    root2 = insert(root2,7); insert(root2,4); insert(root2,2);
    insert(root2,5); insert(root2,9); insert(root2,8);
    cout << "Median (even): " << findMedian(root2) << endl;
    return 0;
}

আউটপুট:

Median (odd): 7
Median (even): 6