Creating red and black tree from two BSTs

Question

As part of my university algorithm course, we were asked the following question:

Given two binary search trees, T1 and T2 (not necessarily balanced). h1 and h2 represent the height of each tree, n1 and n2 represent the number of elements in each tree.
Write an algorithm that merges the two trees into one red black tree. Time complexity required is θ(max(n1, n2)). Space complexity required is θ(max(h1, h2)).

Note: the RBT should be created from the existing nodes of T1 and T2.

The nodes of the binary trees already have the color property, and they are all set to red. We should obviously change them accordingly when creating the RBT.

So far I am not bad at those type of question, but this time I’m a bit clueless…

I was thinking of changing the pointers of the trees into linked list for each level and to store a pointer to the head of each list at an array of size h, but I can't find a way to merge those linked list into one red black tree at time complexity of θ(n).

Answer 1

Here is a sketch of an algorithm:

For each of the given BSTs create an inorder iterator, which which you can traverse nodes in their proper value order.

Combine these two iterators into one (much like with merge sort), so that it produces nodes in their proper value order.

As you know that the target tree will have = ₁+₂ nodes, you can aim for a shape of the target tree that is complete, i.e. where all levels are fully populated, except maybe for the bottom layer, which will be populated such that all its nodes are at the left side of that layer.

Using an array with an entry per level in the target tree (that still is to be populated), you can track the path to where the next node should be placed. The first node should be placed at the bottom layer, the next node should be its parent, the one after that should be its sibling, ...etc. As you do that traversal on the input trees and get nodes from it, use those nodes for creating the target tree with the help of this array (so the tree builds up in in-order fashion).

Take care that the iterators over the input trees do not get "disoriented" by the reuse of the yielded nodes in the target tree: make sure the cursors move one step ahead before the "current" node gets mutated into its target position.

Color all nodes black, except for the nodes in the bottom layer when it is not completely filled -- those should be red. This way the tree fulfils the red-black property.

All those actions can be done with θ() time complexity, which is equivalent with θ(₁+₂) or θ(max(₁,₂)).

The space complexity (not counting the existing nodes) is determined by the inorder traversal (both in reading and writing) which needs to maintain the path from the root to the current node, so that we have a space complexity of θ(ℎ₁+ℎ₂), again equivalent with θ(max(ℎ₁,ℎ₂)).

Implementation

Here is an implementation in JavaScript of the above described algorithm:

class Node {
    isRed = true; // Not relevant for plain BST trees
    left = null;
    right = null;
    value;
    
    constructor(value) {
        this.value = value;
    }
}

class Bst {
    root = null;
    size = 0;
    
    constructor(...values) { // Any number of values can be passed: they will be inserted
        for (const value of values) {
            this.insert(value);
        }
    }
    
    insert(value) { // Standard BST insertion
        this.size++;
        if (!this.root) {
            this.root = new Node(value);
        } else {
            let node = this.root;
            while (true) {
                if (value < node.value) {
                    if (!node.left) {
                        node.left = new Node(value);
                        return;
                    }
                    node = node.left;
                } else {
                    if (!node.right) {
                        node.right = new Node(value);
                        return;
                    }
                    node = node.right;
                }
            }
        }
    }
    
    printRec(node, tab) {
        if (!node) return;
        this.printRec(node.right, tab + "  ");
        console.log(tab, node.value, node.isRed ? "red" : "black");
        this.printRec(node.left,  tab + "  ");
    }
    
    print(message="tree") {
        console.log(message + ":");
        this.printRec(this.root, "");
    }
    
    getCursor() {
        return new BstCursor(this);
    }
    
    static merge(one, other) { // Does not create new nodes; destroys the two input trees
        const tree = new Bst();
        const size = one.size + other.size;
        let height = Math.floor(Math.log2(size));
        // Number of nodes to be placed in the bottom level of the new tree:
        let bottomCount = (size + 1) - (1 << height);
        const path = Array(height + 1).fill(null);
        // Depth that the next node will have in the new tree 
        let depth = height; 
        const cursor1 = one.getCursor();
        const cursor2 = other.getCursor();
        while (true) {
            // Choose which cursor has a current node with the least value
            const cursor = cursor1.done() || !cursor2.done() && cursor1.current().value > cursor2.current().value
                        ? cursor2 : cursor1;
            const node = cursor.current();
            cursor.next(); // Move to the next, so that the mutation of the current node will not affect traversal
            // Isolate the node. Its left child was already processed, 
            //    and we just moved the cursor, so for the cursor this node is no longer needed
            node.left = node.right = null;
            path[depth] = node;
            if (depth + 1 < path.length && path[depth+1]) { // Is there a left child to link?
                node.left = path[depth+1];
                path[depth+1] = null;
            }
            if (depth < height) {
                node.isRed = false;
                depth = height; // Next node will be a leaf
            } else {
                bottomCount--;
                node.isRed = bottomCount >= 0; // Only nodes at the bottom level are red
                if (bottomCount == 0) height--; // Bottom level has been covered, remaining part has one less level
                depth--;
                while (path[depth]) {
                    path[depth].right = path[depth+1];
                    path[depth+1] = null;
                    if (!depth) {
                        tree.root = path[0];
                        one.root = other.root = null; // cleanup
                        return tree;
                    }
                    depth--;
                }
            }
        }
    }
}

class BstCursor { // In-order traversal cursor for a given BST
    stack = [];
    
    constructor(bst) {
        this.descendToMin(bst.root);
    }
    
    descendToMin(node) {
        while (node) {
            this.stack.push(node);
            node = node.left;
        }
    }
    
    current() {
        return this.stack.at(-1);
    }

    next() {
        if (!this.done()) this.descendToMin(this.stack.pop().right);
    }
    
    done() {
        return !this.stack.length;
    }
}

// Example run
let bst1 = new Bst(7, 4, 2, 14, 6, 1, 18, 10, 13, 16);
let bst2 = new Bst(11, 5, 12, 0, 17, 3, 15, 8);
bst1.print("first tree");
bst2.print("second tree");
const result = Bst.merge(bst1, bst2);
result.print("merged tree");