Tree Traversals

Binary tree-র প্রতিটি node ঘুরে দেখার চারটি উপায়, আর কেন প্রতিটিতে order আলাদা হয়।

মূল ধারণা (কোম্পানির org chart)

Tree অনেকটা org chart-এর মতো: উপরে একজন boss, আর প্রত্যেকের নিচে সর্বোচ্চ দুজন direct report থাকে (একটি left আর একটি right child)। "Traversal" মানে প্রত্যেককে ঠিক একবার করে ঘুরে দেখা। প্রশ্ন শুধু একটাই: কখন কাউকে visit করবেন:

তিনটি recursive version আসলে একই function, শুধু visit লাইনের জায়গা বদলায়। লক্ষ করুন, নিচে নামার সময় call stack বড় হয় আর call return করলে ছোট হয়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: প্রতিটি node একবারই visit হয়, তাই time complexity node-সংখ্যার সাথে সমান হারে বাড়ে (O(n))। Recursive version-এ space লাগে tree-র height-এর সমান; level-order-এ space লাগে সবচেয়ে চওড়া level-এর সমান।