Reordering a binary search tree within the tree itself

Squarepeg 0
Viewed 23

If I am given a binary tree that is unordered, what would be the best method of ordering it without just creating a new tree? When I say ordered, I mean such that all nodes in a left subtree is less than the root node and all nodes in a right subtree is greater than the root node.

I appreciate that the most optimal way to make an undordered binary tree into a binary seach tree is to extract all the nodes then insert them into a new tree, but is there another approach involving switching the placement of nodes in the original tree that could be done algorithmically?

binary-search-tree binary-tree
1 Answers

The method of creating a new tree is certainly the way to go, but just as an excercise, it is possible to sort a binary tree in-place.

You could for instance implement bubble sort, such that all nodes remain in place, but their values are swapped in the process.

For this to work you need to implement an inorder traversal. Then keep repeating a full inorder traversal, where you compare the values of two successively visited nodes, and swap their values if they are not in the right order. When an inorder traversal does not result in at least one swap, the tree is sorted and the process can stop.

Here is an implementation in JavaScript:

It first generates a tree with 10 nodes having randomly unsigned integers below 100. The shape of the tree is random too (based on a random "path" that is provided with each insertion)

Then it sorts the tree as described above. As JavaScript has support for generators and iterators, I have used that syntax, but it could also be done with a callback system.

It displays the tree in a very rudimentary way (90° rotated, i.e. with the root at the left side), as it is before and after the sort operation.

class Node {
    constructor(value) {
        this.value = value;
        this.left = this.right = null;
    }
}

class Tree {
    constructor() {
        this.root = null;
    }
    // Method to add a value as a new leaf node, using the 
    //   binary bits in the given path to determine 
    //   the leaf's location:
    addAtPath(value, path) {
        function recur(node, path) {
            if (!node) return new Node(value);
            if (path % 2) {
                node.right = recur(node.right, path >> 1);
            } else {
                node.left = recur(node.left, path >> 1);
            }
            return node;
        }
        this.root = recur(this.root, path);
    }
    *inorder() {
        function* recur(node) {
            if (!node) return;
            yield* recur(node.left);
            yield node;
            yield* recur(node.right);
        }
        yield* recur(this.root);
    }
    toString() {
        function recur(node, indent) {
            if (!node) return "";
            return recur(node.right, indent + "   ")
                 + indent + node.value + "\n"
                 + recur(node.left, indent + "   ");
        }
        return recur(this.root, "");
    }
    bubbleSort() {
        let dirty = true;
        while (dirty) {
            dirty = false;
            let iterator = this.inorder();
            // Get first node from inorder traversal
            let prevNode = iterator.next().value;
            for (let currNode of iterator) { // Get all other nodes
                if (prevNode.value > currNode.value) { 
                    // Swap
                    const temp = prevNode.value;
                    prevNode.value = currNode.value;
                    currNode.value = temp;
                    dirty = true;
                }
                prevNode = currNode;
            }
        }
    }
}

// Helper
const randInt = max => Math.floor(Math.random() * max);

// Demo:
const tree = new Tree();
for (let i = 0; i < 10; i++) {
    tree.addAtPath(randInt(100), randInt(0x80000000));
}
console.log("Tree before sorting (root is at left, leaves at the right):");
console.log(tree.toString());
tree.bubbleSort();
console.log("Tree after sorting:");
console.log(tree.toString());

The time complexity is O(n²) -- typical for bubble sort.

This sorting does not change the shape of the tree -- all nodes stay where they are. Only the values are moved around.

trincot0
Related