# Merge K BST of N elements in total into a single RBT in O(N log K) time

I have the following question to solve;

Given $$K$$ BST consisting of $$N$$ total elements, show how you can create a Red Black Tree in $$O(N\log K)$$ time.

I had the following idea but it falls on the last part of insertion into the red black tree;

Get an inorder scan of each BST (total of $$O(N)$$) into lists. From each list pick the smallest element (the min) and insert it along with the index of the list it originated from (the key-value pair (value,list_index))into an auxiliary min-heap.
Extract the min value from the auxiliary heap and insert it into the RBT. Now take the next element from the list_index list and insert it into the heap.

So the building of the min-heap will take $$O(K\log K)$$ time ($$K$$ insertions into the min heap which at most will take $$\log K$$ time).
Extracting the min $$N$$ times will take $$O(N\log K)$$ time.
Inserting into the RBT $$N$$ times will take $$O(N\log N)$$ time <-- This is the issue.

As I understand it - the first insertion will take $$O(\log 1)$$, the next $$O(\log 2)$$, etc. until we have inserted all $$N$$ elements - resulting in a total of $$O(N\log N)$$ instead of the desired $$O(N\log K)$$.

Anyone has any idea how to perform this in the wanted time or where my solution is wrong?

Your idea of maintaining a min-heap of $$K$$ elements of the form (value,list_index) is great.
Initialize an empty list of capacity $$N$$. Append the extracted min value from the auxiliary heap to the list every time instead. The initialization and all $$N$$ appendments cost $$O(N)$$ time.
From the list at last, which is a sorted list of $$N$$ elements, we can build an RBT in $$O(N)$$ time. (In fact, given a sorted list of $$N$$ elements, we can build any given type of BST in $$O(N)$$ time. Or any type of BST that I know of).
• So, just so I have the full picture, since my book does not cover how to build an RBT in O(N). I will take this list and recursively build a balanced BST from it (take the middle element, then the middle of the left, middle of the right and so on). Then - if N = (2^h) -1 -> color all nodes black ; else, then for some h N< (2^h) -1, color all 2^(h-1) in black and the rest in red. Is that right? Commented May 5, 2023 at 14:35
• Right basically. Minor correction, for some integer $h$ such that $2^{h-1}-1< N<2^h-1$, color all $2^{h-1}-1$ nodes (that are of depth $<h$) in black and the rest in red. Commented May 5, 2023 at 14:54