La conversion d'un arbre binaire de recherche (BST) en une liste doublement chaînée triée est un problème classique d'algorithmique. L'objectif est de réorganiser les pointeurs de l'arbre (gauche et droite) pour qu'ils fassent office de pointeurs de liste (précédent et suivant), tout en conservent l'ordre croissant des éléments sans allouer de nouveaux nœuds.

Approche Algorithmique

La propriété fondamentale d'un arbre binaire de recherche est qu'un parcours enfixe (in-order traversal) permet de visiter les nœuds dans un ordre strictement croissant. Pour transformer l'arbre en liste, nous devons :

1. Effectuer un parcours infixe de manière récursive.
2. Maintenir une référence vers le dernier nœud traité (le nœud précédent).
3. Modifier le pointeur gauche du nœud actuel pour qu'il pointe vers le précédent.
4. Modifier le pointeur droite du nœud précédent pour qu'il pointe vers l'actuel.

Implémentation pour une Liste Doublement Chaînée Standard

Dans cette version, nous transformons l'arbre en une liste linéaire où le premier élément a son pointeur gauche à nul et le dernier son pointeur droite à nul.

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void tisserLiens(Node* actuel, Node*& dernier) {
        if (actuel == nullptr) return;

        // Traitement du sous-arbre gauche
        tisserLiens(actuel->left, dernier);

        // Liaison du nœud actuel avec le précédent
        actuel->left = dernier;
        if (dernier != nullptr) {
            dernier->right = actuel;
        }
        dernier = actuel;

        // Traitement du sous-arbre droit
        tisserLiens(actuel->right, dernier);
    }

    Node* transformerEnListe(Node* racine) {
        if (racine == nullptr) return nullptr;

        Node* dernierElement = nullptr;
        tisserLiens(racine, dernierElement);

        // Recherche de la tête de la liste (le nœud le plus à gauche)
        Node* tete = racine;
        while (tete && tete->left) {
            tete = tete->left;
        }
        return tete;
    }
};

Implémentation pour une Liste Doublement Chaînée Circulaire

Certaines variantes du problème demandent que la liste soit circulaire, reliant ainsi le plus petit élément au plus grand.

class SolutionCirculaire {
private:
    Node* premier = nullptr;
    Node* dernier = nullptr;

public:
    void parcoursRecursif(Node* courant) {
        if (!courant) return;

        parcoursRecursif(courant->left);

        if (dernier) {
            // Établir le lien bidirectionnel entre le précédent et l'actuel
            dernier->right = courant;
            courant->left = dernier;
        } else {
            // Premier nœud rencontré (le plus petit)
            premier = courant;
        }
        dernier = courant;

        parcoursRecursif(courant->right);
    }

    Node* bstToCircularList(Node* root) {
        if (!root) return nullptr;

        parcoursRecursif(root);

        // Fermeture de la boucle circulaire
        premier->left = dernier;
        dernier->right = premier;

        return premier;
    }
};

Analyse de Complexité

• Complexité Temporelle : O(N), où N est le nombre de nœuds dans l'arbre. Chaque nœud est visité exactement une fois lors du parcours infixe.
• Complexité Spatiale : O(H), où H est la hauteur de l'arbre. Cela correspond à la profondeur de la pile d'appels récursifs. Dans le pire des cas (arbre dégénéré), cela peut être O(N), tandis que pour un arbre équilibré, cela sera O(log N).