- বাইনারি ট্রি (Binary Tree): যেসব ট্রি তে সাবট্রি দুটির বেশী থাকেনা তাকে বাইনারি ট্রি বলে। অর্থাৎ, যেকোন নোডের সাবট্রি ০,১,২ যেকোনটি হতে পারে।
 |
| বাইনারি ট্রি |
1. Complete binary Tree: যেসকল বাইনারি ট্রি বাম পাশ থেকে পূর্ণ হয়ে ডানপাশে এসে শেষ হয় তাকে কমপ্লিট বাইনারি ট্রি বলে ।
2. Full Binary Tree: যেসকল বাইনারি ট্রি'র প্রত্যেকটি নোডে দুইটা করে সাব ট্রি থাকে তাকে ফুল বাইনারি ট্রি বলে। দুইটার কম থাকলে তা কখনো Full binary Tree হবেনা।
• Maximum Number of node On a level: কোন লেবেলে বড়জোর 2^i সংখ্যক নোড থাকতে পারে। যেখানে i হল লেবেল নাম্বার!
যখন, i=0; জিরো লেবেলে 1 টা নোড ;
যখন, i=1; 1 নং লেবেল 2 টা নোড থাকতে পারবে। এভাবে যেতে থাকবে।
• Maximum Number of node on a Tree: কোন ট্রিতে সরবোচ্চ নোড সংখ্যা হবে 2^0 থেকে শুরু করে 2^h পর্যন্ত সংখ্যাগুলোর যোগফল। যেখানে, H হল সরবোচ্চ লেবেল নাম্বার।
i.e: fig-2
2^0+2^1+2^2=7
অর্থাৎ, দ্বিতীয় চিত্রে সরবচ্চ ৭ টি নোড থাকতে পারবে।
Tree To array: ট্রি থেকে অ্যারেতে রুপান্তর সময় কয়েকটা জিনিস খেয়াল রাখতে হবে।
১। প্রথবার root->left->right তারপর থেকে left->right ; এভাবে লেবেল বাই লেবেল ট্র্যাভারস করবে ।
২। সবসময় ট্রি এর প্রতিটি নোডকে দুইটা সাবট্রি(child) বিবেচনা করতে হবে। মানে হল প্রত্যেকটি লেবেল কমপ্লিট বিবেচনা করতে হবে(2^i) । যেমন, 0 লেবেলে 2^1 টি 1নং লেবেলে 2^1 টি ,2 নং লেবেলে 2^2 টি এভাবে। যদি কোন লেবেল অসম্পূর্ণ থাকে তাহলে সে যায়গায় খালি রেখে অ্যারে সম্পূর্ণ করতে হবে। চিত্রটি লক্ষ করলে ব্যাপারটা ক্লিয়ার হবে ।
 |
| চিত্রঃ ট্রি থেকে অ্যারে তে রুপান্তর |
