Columns and zigzags

Questions 1 to 5 of 8

1. 1. Build tree X with the node(value, left, right) helper, which is TreeNode(value, left, right) from this lesson, then run vertical_order from this lesson. ``python x = node(8, node(3, node(1, None, None), node(6, node(4, None, None), node(7, None, None))), node(10, None, node(14, node(13, None, None), None))) print(vertical_order(x)) `` What does the program print?

   [[1], [3, 4], [6, 8], [10, 7, 13], [14]][[1], [3, 4], [8, 6], [10, 13, 7], [14]][[1], [3, 4], [8, 6], [10, 7, 13], [14]][[1], [3, 4], [8, 6], [10, 7, 13, 14]]
2. 2. Using tree X from the previous question, what does zigzag_reverse print? Levels are counted from 1 at the root. ``python print(zigzag_reverse(x)) ``

   [[8], [10, 3], [1, 6, 14], [13, 7, 4]][[8], [3, 10], [1, 6, 14], [4, 7, 13]][[8], [10, 3], [14, 6, 1], [13, 7, 4]][[8], [10, 3], [1, 6, 14], [4, 7, 13]]
3. 3. Using tree X again, what does boundary print? ``python print(boundary(x)) ``

   [8, 3, 1, 4, 7, 14, 13, 10][8, 3, 6, 1, 4, 7, 13, 14, 10][8, 3, 1, 4, 7, 13, 10, 14][8, 3, 1, 4, 7, 13, 14, 10]
4. 4. Why does zigzag_reverse reverse only the printed list of a level, and not the queue?

   reverse() can only be called on a list, so the level must be copied out firstThe children of a level must stay in left-to-right order in the queue, because the next level is read from itA queue cannot hold more than one level, so the reversal has to happen before any children are addedReversing the queue would print the root last, so the output would start from the bottom
5. 5. Why does the top view use setdefault instead of plain assignment (top[col] = value)?

   setdefault is faster, so the walk over a large tree takes less timePlain assignment would raise an error the second time a column is seenPlain assignment keeps negative columns out of the dict, so the left side would be missingThe breadth-first walk reaches the highest node of each column first, and setdefault keeps that first value