একটি পজিটিভ পূর্ণসংখ্যা L দেওয়া আছে যা পারফেক্ট বাইনারি ট্রির লেভেল (level) সংখ্যা নির্দেশ করে। এই ট্রির লীফ নোডগুলো ১ থেকে n পর্যন্ত নম্বর করা আছে। যেখানে n হলো লীফ নোডের সংখ্যা। প্যারেন্ট নোড হলো চাইল্ড নোডগুলোর যোগফল। আমাদের এই পারফেক্ট বাইনারি ট্রির সকল নোডের যোগফল প্রিন্ট করতে হবে। যদি ট্রি নিচের মত হয়:
তবে মোট যোগফল ৩০।
নিকট থেকে দেখলে, সকল নোডের যোগফল বের করতে হবে। যেহেতু লীফ নোডগুলো ১ থেকে n পর্যন্ত মান ধারণ করে, তাই n(n+1)/2 ফর্মুলা দিয়ে লীফ নোডগুলোর যোগফল বের করা যায়। যেহেতু এটি পারফেক্ট বাইনারি ট্রি, তাই প্রতিটি লেভেলের যোগফল সমান হবে। তাই লাস্ট লেভেলের যোগফল বের করে লেভেল সংখ্যা দিয়ে গুণ করলেই চূড়ান্ত যোগফল পাওয়া যাবে।
উদাহরণ
#include<iostream> #include<cmath> using namespace std; int treeSum(int level) { int total_leaves = pow(2, level - 1); int leaf_sum = 0; leaf_sum = (total_leaves * (total_leaves + 1)) / 2; int sum = leaf_sum * level; return sum; } int main() { int levels = 4; cout << "Sum of all nodes for a perfect binary tree with level " << levels << " is: " << treeSum(levels); }আউটপুট
Sum of all nodes for a perfect binary tree with level 4 is: 144
