Trees from traversals

Questions 1 to 5 of 8

1. 1. The preorder-and-inorder rebuild handles one call on a non-empty preorder range. Put its steps in the order the code runs them.

   Use the arrows to put the steps in order.

   1. 1.Look up the root's position in the inorder map, called mid↑↓
   2. 2.Compute the left size as mid minus the start of the inorder range↑↓
   3. 3.Build the left subtree from the next left-size values of preorder↑↓
   4. 4.Build the right subtree from the values after them↑↓
   5. 5.Read the root from the first value of the preorder range↑↓
2. 2. Put these steps of one buildRange call in the inorder-and-postorder rebuild in order. The call gets a non-empty inorder range.

   Use the arrows to put the steps in order.

   1. 1.Look up the root's position in inorder and check that it is inside the range↑↓
   2. 2.Build the right subtree from the inorder range after the root↑↓
   3. 3.Return the new node↑↓
   4. 4.Take the value at the current postorder index as the root, then move the index back by one↑↓
   5. 5.Build the left subtree from the inorder range before the root↑↓
3. 3. In the lesson's table of calls for the seven-node example, which root value does call 4 take?

   Type your answer.

4. 4. The map from each inorder value to its position in the preorder-and-inorder rebuild is a std::______. Fill in the blank with the container's name.

   Type your answer.

5. 5. The rebuild is called like this, and then the tree is written out in marker format. Each node is written in preorder, with # for each empty spot, joined by commas. ``cpp auto root = build_tree({8, 4, 2, 6, 12}, {2, 4, 6, 8, 12}); `` What is the written text?

   8,2,#,#,4,6,#,#,12,#,#2,4,6,8,128,4,2,#,#,6,#,#,12,#,#8,4,#,#,6,2,#,#,12,#,#