বিবিএস-এর প্রি-অর্ডার ট্রাভার্সাল ব্যবহার করে রুট চেয়ে ছোট উপাদানগুলির সংখ্যা বের করা

আপনাকে বাইনারি সার্চ ট্রি (বিবিএস)-এর প্রি-অর্ডার ট্রাভার্সালের ফলাফল দেওয়া হয়েছে। আপনাকে বের করতে হবে কতগুলো উপাদান রুট চেয়ে ছোট।

উদাহরণ

ইনপুট:

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

আউটপুট:

রুট হলো ৫, এবং এর চেয়ে ছোট তিনটি উপাদান রয়েছে: ৪, ২, ১।

অ্যালগরিদম

প্রি-অর্ডার ফলাফলটি একটি অ্যারেতে সংরক্ষণ করুন।
প্রথম উপাদানটি (রুট) একটি ভেরিয়েবলে রাখুন।
দ্বিতীয় উপাদান থেকে শুরু করে লুপ চালান।
প্রতিটি উপাদান রুটের সাথে তুলনা করুন।
যদি বর্তমান উপাদান রুট চেয়ে ছোট হয়, তবে কাউন্ট বাড়ান।
শেষে কাউন্ট ফেরত দিন।

সি++ ইমপ্লিমেন্টেশন

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

int getElementsCount(int arr[], int n) {
    if (n <= 0) return 0;
    int root = arr[0], count = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] < root) count++;
    }
    return count;
}

int main() {
    int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
    int n = 8;
    cout << getElementsCount(preorder, n) << endl;
    return 0;
}