Transform any Binary Search Tree in to a Sorted Linked List

mgcadmin 24-10-2024

The relationship between binary search trees and linked lists is no secret. Without the use of some self balancing scheme any binary search tree has the potential to "devolve" into a linked list if subjected to a series of insertions in sorted order. It is also well known that  any binary search tree can be transformed into any other binary search tree by employing the correct application of left and right rotations to the tree. 

With this in mind, we can then surmise that we should be able to transform any binary search tree into a sorted linked list using nothing but rotations. In todays post I'm going to show how to easily perform this transfomation. The examples dicussed will be built and displayed using the following code for binary search trees:

struct node {
    int key;
    node* left;
    node* right;
    node(int i) : key(i), left(nullptr), right(nullptr) { }
};

typedef node* link;

link put(link h, int v) {
    if (h == nullptr) {
        return new node(v);
    }
    if (v < h->key) h->left = put(h->left, v);
    else h->right = put(h->right, v);
    return h;
}

void preorder(link h) {
    if (h != nullptr) {
        cout<<h->key<<" ";
        preorder(h->left);
        preorder(h->right);
    }
}

 

Rotations

Rotations in binary search tree's allow us to rearrange the nodes position in the tree's while maintaining the search tree property invariant that an inorder traversal of the tree yields the keys in ascending sorted order. When we perform a rotation on a node, we are in effect making one of the current nodes child nodes (which one depends on the direction of the rotation) into the current nodes parent node.

link rotR(link h) {
    link x = h->left;
    h->left = x->right;
    x->right = h;
    return x;
}

link rotL(link h) {
    link x = h->right;
    h->right = x->left;
    x->left = h;
    return x;
}

Both left and right rotations are mirror images of each other. To convert a binary search tree into a linked list, we only need to perform right rotations.

Flattening The Tree

The actual transformation of the tree into a linked list, or the "flattening" of the tree is a simple process that works by starting from the root and making sure that no node in the tree has a left child. This leaves our tree in sorted order that a preorder and inorder traversal produce the same results. The only real "gotcha" is the need to create a dummy root node, assigning the actual root node to it's right child. With this done, we work our way down the right side of the tree, rotating any left subtree around it's parent until every node has only right children.

link flatten(link root) {
    link pr = new node(1);
    pr->right = root;
    link tail = pr;
    link rest = tail->right;
    while (rest != nullptr) {
        while (rest->left) {
            rest = rotR(rest);
            tail->right = rest;
        }
        tail = rest;
        rest = rest->right;
    }
    return pr->right;
}

int main(int argc, char* argv[]) {
    int values[] = { 42, 86, 24, 11, 73, 101, 6, 52, 3, 88};
    link root = nullptr;
    for (int v : values) {
        root = put(root, v);
    }
    preorder(root);
    cout<<endl;
    root = flatten(root);
    for (link it = root; it != nullptr; it = it->right)
        cout<<it->key<<" ";    
    cout<<endl;
    return 0;
}

max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./clarks
42 24 11 6 3 86 73 52 101 88 
3 6 11 24 42 52 73 86 88 101
max@MaxGorenLaptop:/mnt/c/Users/mgoren$

Ok, so now that we have a sorted linked list, now what? Well, to tell you the truth this algorithm is more of academic interest than actual utility. It serves as the first half of the Day-Stout-Warren algorithm, the second part of which is to take said sorted list, and transform it into a perfectly balanced BST. Scapegoat tree's - a data structure of more academic interest than practical importance - perform localized balancing in the same way.

Well, thats what I've got for today, I thought I would keep it light with a simple but fun algorithm. Until next time, Happy Hacking!

---