বাইনারি সার্চ ট্রিকে সিঙ্গলি লিঙ্কড লিস্টে রূপান্তর C++-এ

একটি বাইনারি ট্রি দিয়ে ইন-প্লেস (in-place) একটি সিঙ্গলি লিঙ্কড লিস্ট তৈরি করতে হবে। লিস্টটি ট্রির ইনঅর্ডার ট্রাভার্সাল অনুযায়ী সাজানো থাকবে।

উদাহরণ

ইনপুট ট্রি:

    1
   / \
  2   5
 / \
3   4

আউটপুট লিস্ট: 1 → 2 → 3 → 4 → 5

অ্যালগরিদম (রিভার্স ইনঅর্ডার)

1. একটি গ্লোবাল পয়েন্টার prev রাখুন (শুরুরে NULL)।
2. রিভার্স ইনঅর্ডার ট্রাভার্সাল করুন: ডান → রুট → বাম।
3. প্রতিটি নোডের জন্য:
   • right = prev
   • left = NULL
   • prev = current node
4. শেষে prev হয়ে যাবে লিস্টের হেড।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

class Solution {
public:
    TreeNode* prev = NULL;
    
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = NULL;
        prev = root;
    }
};

int main() {
    // Tree construction: 1,2,5,3,4 (level order)
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    
    Solution ob;
    ob.flatten(root);
    
    TreeNode* ptr = root;
    while (ptr != NULL) {
        cout << ptr->val << " ";
        ptr = ptr->right;
    }
    return 0;
}

ইনপুট

{1,2,5,3,4}

আউটপুট

1, 2, 3, 4, 5,