Sorted inputs and balanced builds

Questions 1 to 5 of 7

1. 1. Using the Node struct and build from this lesson, and a preorder function that prints each key, then walks the left subtree, then the right subtree, what does this code print? ``cpp vector<int> a = {1, 2, 3, 4, 5}; auto root = build(a, 0, static_cast<int>(a.size())); preorder(root.get()); ``

   3 2 1 4 53 2 1 5 43 1 2 5 42 1 3 5 4
2. 2. The Node struct, build and height from this lesson are used by this code. What does it print? ``cpp vector<int> b = {1, 2, 3, 4, 5, 6}; auto root = build(b, 0, 6); cout << "root " << root->key << ", height " << height(root.get()) << '\n'; ``

   root 3, height 3root 4, height 2root 4, height 3root 4, height 4
3. 3. A plain binary search tree, with no rebuilding, gets the keys 1 to n inserted one at a time, in that order. How does the total number of comparisons for all n inserts grow as n gets larger?

   O(n^2)O(n)O(n log n)O(log n)
4. 4. A plain binary search tree gets the keys 1 to 20 inserted one at a time, in that order, with no rebuilding. What is the total number of comparisons made by all 20 inserts?

   Type a number.

5. 5. True or false: a balanced build from the sorted keys 1 to 1000 gives a tree of height 10.

   True, because bit_width(1000) is 10, and the height of a balanced build equals bit_width(n)False, because each level halves the keys, so 1000 keys need 500 levels