Trees from traversals

Questions 1 to 5 of 8

1. 1. When rebuilding a tree from inorder and postorder lists, what are the steps for one call, in order?

   Use the arrows to put the steps in order.

   1. 1.Build the right subtree from the inorder values after the root↑↓
   2. 2.Build the left subtree from the inorder values before the root↑↓
   3. 3.Find the root's position in the inorder range↑↓
   4. 4.Take the last unused value of the postorder list as the root↑↓
2. 2. In the preorder and inorder build, the left subtree has mid - ___ nodes, where mid is the root's position in the inorder list. Fill in the blank.

   Type your answer.

3. 3. This code runs the preorder and inorder build from this lesson. What does it print? ``python root = build_tree([5, 2, 8, 1], [2, 5, 1, 8]) pre = [] preorder_of(root, pre) print('preorder: ' + str(pre)) ``

   [2, 5, 1, 8][5, 2, 8, 1][2, 1, 8, 5][5, 2, 1, 8]
4. 4. When rebuilding a tree from preorder and inorder lists, what are the steps for one call, in order?

   Use the arrows to put the steps in order.

   1. 1.Find the root's position mid in the inorder range↑↓
   2. 2.Build the left subtree from the next preorder values and the inorder values before mid↑↓
   3. 3.Compute the left size as mid - in_start↑↓
   4. 4.Take the first value of the current preorder block as the root↑↓
   5. 5.Build the right subtree from the preorder values after the left block and the inorder values after mid↑↓
5. 5. Why does a preorder list alone not describe one tree?

   Preorder lists skip the leaves, so some nodes are missingTrees with different values can give the same preorder, so the values decide the shapeTwo different trees can give the same preorder list, such as root 1 with a left child 2, and root 1 with a right child 2Preorder always lists the values in sorted order, so trees with the same values look the same