Problem

Consider building two binary search trees containing the integer keys 1 to 63, inclusive, received in the orders

(a) all the odd integers in order (1, 3, 5, ... , 63), then 32, 16, 48, then the remaining even integers in order (2, 4, 6, ...).

(b) 32, 16, 48, then all the odd integers in order (1, 3, 5, ... , 63), then the remaining even integers in order (2, 4, 6, ...).

Which of these trees will be quicker to build? Explain why. [Try to answer this question without actually drawing the trees.]