Q13a

Consider the height-balanced tree $T_{t}$ with values stored at only the leaf nodes, shown in Fig$.4.$

(i) Show how to merge to the tree, $T_{1}$ elements from tree $T_{2}$ shown in Fig$.5$ using node D of tree $T_{1}$.

(ii) What is the time complexity of a merge operation of balanced trees $T_{1}$ and $T_{2}$ where $T_{1}$ and $T_{2}$ are of height $h_{1}$ and $h_{2}$ respectively, assuming that rotation schemes are given. Give reasons.