Question is based on Trees where it has coordinates
3. (5 pts.) Drawing Trees on a grid. When drawing trees on a grid, each node must be assigned an 2- and y-coordinate. Edges are then drawn between a node and its children. For binary trees, there is a simple and elegant way of assigning nodes their coordinates so that the resulting drawing is nice. For each node v, let its x-coordinate be i if v is the ith node processed by an inorder traversal of the tree; let its y-coordinate be -j if the depth of u in the tree is j. The binary tree below is drawn using the said 2- and y-coordinates. For example, r has coordinates (12,0), d has coordinates (10,-2) while s has coordinates (17,-4). 2 The above technique though does not generalize to arbitrary trees - inorder traversals are only meaningful on binary trees. So we need to design a more flexible algorithm. But first, let's clarify what it means for a grid drawing of a tree to be "nice." For the rest of the problem, assume that references to the children of each node v is stored in v.children. The children are also ordered - that is, there is a first child, a second child, etc. - and the children are accessed in the said order. Lastly, assume that every node has an an even number of children, like quadtrees or octrees, etc. Here are the rules: Each node is assigned integer - and y-coordinates. Two nodes that have the same depth in T are assigned the same y-coordinate. When node v has 2k children, the first k children and their subtrees have x-coordinates smaller than v's c-coordinate while the second set of k chlldren and their subtrees have x-coordinates larger than u's z-coordinate. a. (1 pt.) Briefly explain why the scheme described earlier for assigning 2- coordinates to the nodes of the binary tree works. b. (1 pt.) For the tree below, assign the nodes 2- and y-coordinates that obey the three rules above. The x-coordinates should range from 1 to 13; the y-coordinates should range from 2 to 0. 3. (5 pts.) Drawing Trees on a grid. When drawing trees on a grid, each node must be assigned an 2- and y-coordinate. Edges are then drawn between a node and its children. For binary trees, there is a simple and elegant way of assigning nodes their coordinates so that the resulting drawing is nice. For each node v, let its x-coordinate be i if v is the ith node processed by an inorder traversal of the tree; let its y-coordinate be -j if the depth of u in the tree is j. The binary tree below is drawn using the said 2- and y-coordinates. For example, r has coordinates (12,0), d has coordinates (10,-2) while s has coordinates (17,-4). 2 The above technique though does not generalize to arbitrary trees - inorder traversals are only meaningful on binary trees. So we need to design a more flexible algorithm. But first, let's clarify what it means for a grid drawing of a tree to be "nice." For the rest of the problem, assume that references to the children of each node v is stored in v.children. The children are also ordered - that is, there is a first child, a second child, etc. - and the children are accessed in the said order. Lastly, assume that every node has an an even number of children, like quadtrees or octrees, etc. Here are the rules: Each node is assigned integer - and y-coordinates. Two nodes that have the same depth in T are assigned the same y-coordinate. When node v has 2k children, the first k children and their subtrees have x-coordinates smaller than v's c-coordinate while the second set of k chlldren and their subtrees have x-coordinates larger than u's z-coordinate. a. (1 pt.) Briefly explain why the scheme described earlier for assigning 2- coordinates to the nodes of the binary tree works. b. (1 pt.) For the tree below, assign the nodes 2- and y-coordinates that obey the three rules above. The x-coordinates should range from 1 to 13; the y-coordinates should range from 2 to 0
