Tree

পাঁচটা সমতুল্য সংজ্ঞা — যেকোনো একটা সত্য হলে বাকি সবগুলোও:

1. Connected এবং acyclic
2. Connected এবং ঠিক n−1 edge
3. Acyclic এবং ঠিক n−1 edge
4. যেকোনো দুই vertex-এর মধ্যে ঠিক একটা path
5. Connected, কিন্তু যেকোনো edge মুছলেই disconnect

প্রতিটা একটা ভিন্ন প্রকৌশল প্রশ্নের উত্তর দিতে সুবিধাজনক: সংজ্ঞা ৪ বলে routing অস্পষ্ট নয়; সংজ্ঞা ৫ বলে কোনো fault tolerance নেই — একটা link গেলেই বিচ্ছিন্ন।

n ≥ 2 হলে অন্তত দুইটা leaf আছে। এই leaf-এর অস্তিত্বই বহু tree algorithm-এর ভিত্তি — সবসময় একটা leaf সরিয়ে ছোট tree-তে নামা যায়।

Tree হলো [[graph]]-এর বিশেষ শ্রেণি, আলাদা structure নয়। তাই graph algorithm tree-তেও চলে। উল্টোটা নয় — tree-র জন্য লেখা recursive traversal (visited set ছাড়া) সাধারণ graph-এ cycle-এ পড়ে infinite loop করে। JSON serializer-এ circular reference error ঠিক এই কারণে।

leaves ≤ 2^height — তাই n leaf রাখতে height অন্তত log₂ n। এটাই balanced BST, comparison sort-এর lower bound আর B-tree fanout — তিনটারই ভিত্তি।