Binary tree-র প্রতিটি node ঘুরে দেখার চারটি উপায়, আর কেন প্রতিটিতে order আলাদা হয়।
মূল ধারণা (কোম্পানির org chart)
Tree অনেকটা org chart-এর মতো: উপরে একজন boss, আর প্রত্যেকের নিচে সর্বোচ্চ দুজন direct report থাকে (একটি left আর একটি right child)। "Traversal" মানে প্রত্যেককে ঠিক একবার করে ঘুরে দেখা। প্রশ্ন শুধু একটাই: কখন কাউকে visit করবেন:
Preorder: আগে node-কে visit করুন, তারপর তার left দিক, তারপর right দিক।
Inorder: আগে left দিক, তারপর node, তারপর right দিক। (Search tree-তে এতে sorted order পাওয়া যায়।)
Postorder: আগে দুই দিক, শেষে node। (Child আগে, parent পরে, যেমন folder tree delete করার সময় হয়।)
Level-order: এক তলা করে, উপর থেকে নিচে। Recursion-এর বদলে queue ব্যবহার করে।
তিনটি recursive version আসলে একই function, শুধু visit লাইনের জায়গা বদলায়। লক্ষ করুন, নিচে নামার সময় call stack বড় হয় আর call return করলে ছোট হয়।
Run করে দেখুন
নিজে চেষ্টা করুন
একই tree-তে চারটি mode-ই run করুন এবং output list মিলিয়ে দেখুন।
4, 2, 6, 1, 3, 5, 7 দিয়ে Inorder run করুন। output-এ কী লক্ষ করলেন?
একদিকে ঝুঁকে থাকা tree বানান: 1, null, 2, null, 3, null, 4। call stack কতটা উঁচু হয়?
nil call গুলো খেয়াল করুন: প্রতিটি অনুপস্থিত child-এর জন্যও একটি call হয়, যা সাথে সাথে return করে।
সাধারণ ভুল
nil check ভুলে যাওয়া।if n == nil { return } ছাড়া কোড nil pointer dereference করে panic করে।
order গুলিয়ে ফেলা। মনে রাখুন: নামটাই বলে দেয় child-এর তুলনায় visit কোথায় বসে (pre = আগে, in = মাঝে, post = পরে)।
খুব গভীর tree। Recursion প্রতি level-এ একটি stack frame নেয়। যে tree আসলে একটা লম্বা chain, সেখানে অনেক stack লাগে, তাই interviewer মাঝে মাঝে iterative version চান।
Complexity, সহজ ভাষায়: প্রতিটি node একবারই visit হয়, তাই time complexity node-সংখ্যার সাথে সমান হারে বাড়ে (O(n))। Recursive version-এ space লাগে tree-র height-এর সমান; level-order-এ space লাগে সবচেয়ে চওড়া level-এর সমান।