Kth with sizes

Questions 1 to 5 of 7

1. 1. On the tree built by inserting 50, 30, 70, 20, 40, 60, 80 and 35 in that order, what size does node 30 store?

   2345
2. 2. On the same 8-value tree (50, 30, 70, 20, 40, 60, 80, 35), what does kth_largest(root, 2) return?

   60708050
3. 3. Put the steps for deleting 30 from the tree 50, 30, 70, 20, 40, 60, 80, 35 in the order the lesson's delete function runs them. Node 30 has two children.

   Use the arrows to put the steps in order.

   1. 1.Delete 35 from the right subtree, which removes the node under 40↑↓
   2. 2.Recompute each size on the way back up to the root↑↓
   3. 3.Copy 35 into the node that held 30↑↓
   4. 4.Find the successor: the smallest key in the right subtree of 30, which is 35↑↓
4. 4. Match each name from this lesson to what it does.

   Choose the matching item for each row.

   size(node)Choose…sets the node's size to 1 plus its two children's sizeswalks one path and uses left_size to choose the sidecalls kth_smallest with size(root) - k + 1returns 0 for None, and the stored size otherwiseupdate(node)Choose…sets the node's size to 1 plus its two children's sizeswalks one path and uses left_size to choose the sidecalls kth_smallest with size(root) - k + 1returns 0 for None, and the stored size otherwisekth_smallest(root, k)Choose…sets the node's size to 1 plus its two children's sizeswalks one path and uses left_size to choose the sidecalls kth_smallest with size(root) - k + 1returns 0 for None, and the stored size otherwisekth_largest(root, k)Choose…sets the node's size to 1 plus its two children's sizeswalks one path and uses left_size to choose the sidecalls kth_smallest with size(root) - k + 1returns 0 for None, and the stored size otherwise
5. 5. What does this print? It uses insert and size from this lesson. ``python root = None for key in [50, 30, 70, 20, 40, 60, 80, 35]: root = insert(root, key) root = insert(root, 45) print(root.size, root.left.size, root.left.right.size) ``

   8 4 29 4 29 5 38 5 3