The following question will explore the possibility of taking two red-black trees with a special property and merging them together into one red- black tree.

(a) Explain how we can store the black height, bh(x), of an rb-tree in the root x. Explain how we can maintain this extra field at no extra cost.

(b) Given two red black trees, T1 and T2 such that every key in T1 is less than every key in T2, give an algorithm to merge T1 and T2 into one tree. Make sure you also explain your time complexity in addition to the algorithm. You should first give an overview of your algorithm and then pseudocode that explains more completely.