স্যাটেলাইট

নির্দেশনা

ভাবুন, আপনাকে একটি বাইনারি ট্রি Alpha Centauri-র দিকে এগিয়ে আসা একটি স্যাটেলাইটে পাঠাতে হবে, আর আপনার ব্যান্ডউইথ সীমিত। যেহেতু এই ট্রিতে কোনো পুনরাবৃত্ত আইটেম নেই, তাই এর প্রি-অর্ডার ও ইন-অর্ডার ট্রাভার্সাল দিয়েই এটিকে অনন্যভাবে উপস্থাপন করা যায়।

ট্রাভার্সালগুলো থেকে ট্রিটি পুনর্গঠন করার জন্য স্যাটেলাইটের সফটওয়্যারটি লিখুন।

একটি প্রি-অর্ডার ট্রাভার্সাল বাম সাবট্রি প্রি-অর্ডারে পড়ার আগে (তাই "pre") বর্তমান নোডের মান পড়ে। এরপর ডান সাবট্রি প্রি-অর্ডারে পড়া হয়।

একটি ইন-অর্ডার ট্রাভার্সাল প্রথমে বাম সাবট্রি ইন-অর্ডারে, তারপর বর্তমান নোড এবং সবশেষে ডান সাবট্রি ইন-অর্ডারে পড়ে। অর্থাৎ বাম থেকে ডানে ক্রমানুসারে।

উদাহরণস্বরূপ, এই ট্রিটির প্রি-অর্ডার ট্রাভার্সাল হলো [a, i, x, f, r]. এই ট্রিটির ইন-অর্ডার ট্রাভার্সাল হলো [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

দ্রষ্টব্য: প্রি-অর্ডার ট্রাভার্সালের প্রথম আইটেমটি সর্বদাই রুট।