Can I have it on python please. a aThano you

1 Introduction Binary trees are a type of data structure that consists of a list of nodes. Each node may have a parent. Each node may also have two children, called here (left_child, right_child). Nodes without a parent are called root nodes. Nodes without children are called leaf nodes. In the example below, node O is a root node, nodes 4,5,6,7,8 are leaf nodes. One of the main techniques for working with binary trees is to traverse the tree, visiting each node in a specific order. One important algorithm for traversing a binary tree is called depth first search. This is the algorithm you will use for this a ssignment. Depth first search explores as far as possible along the left_child path. When there are no more left children to explore, the algorithm backs out to the right_child and continues exploring. The depth first search algorithm is typically implemented using recursion. For the example tree shown in Figure 1, the depth first search order would be (7,8,3,4,1,5,6,2,0]. Figure 1 X binary tree with 9 nodes 0 generation 2 H 0.0 0.5 1.0 115 2.0 2.5 3.0 3.5 4.0 Figure 1: Example binary tree with 9 nodes. The root node (0) has no parent. The leaf nodes are [4,5,6,7,8). Your submission will produce the same plot formatting, but with the number of nodes computed as specified in the problem specification. Note the alignment on the text nodes (center for root, right aligned for loft_child and Mettalioned forint child the vaxis is invented in that reasonanerations ander down the man with ticks Figure 1: Example binary tree with 9 nodes. The root node (0) has no parent. The leaf nodes are [4,5,6,7,8). Your submission will produce the same plot formatting, but with the number of nodes computed as specified in the problem specification. Note the alignment on the text nodes (center for root, right aligned for left child and left aligned for right_child. The y axis is inverted so that increasing generations render down the page, with ticks draw only at integer generation values. The number of nodes in the binary tree was calculated using the function my NumberOfNodes('me 123@drexel.edu) For this programming assignment, you will develop a Python class that implements the functions and data management associated with binary trees. The programming template contains a list of the class methods and member variables that you must implement. 1 2 3 4 Algorithm 1: Traversing a binary tree with depth first search to set (x,y) render locations for each node. Result: A list of node_ids in depth first search order, with x and y values for each node Initialize the binary tree structure with N nodes, initialize a variable XMAX to store the rightmost leaf node found so far, and call dfs Traverse Initially on the root node. def af e Traverse (node, XMAX=0, y=0) #node has children #traverso left child farat (dfs, XMAX) = dfsTraverse (node.left child, XMAX.child.y) # we get to this line after all our descendents left_children have been processed (dfs, XMAX) - dfsTraverse (node.left_child.XMAX,child-y) #Bet parent node locations stday between children node * = (node.left_child.x+node right_child. 2)/2.0 mode.yey i node has no children bet la location at next integer Vio node.x- XMAX ve increment y at each generation the root in a yo 10 2 72 100% + 7 9 10 11 12 # set parent node locations midway between children node.x = (node.left_child.x+node.right_child.x)/2.0 node.y=y # if node has no children, set leaf location at next integer value node.x = XMAX # we increment y at each generation, so the root is at y=0, its children are at y=1, etc... node.y = y XMAX += 1 # after processing children, add node to dfs list dfs.append (node) return (afs , XMAX) 13 14 15 16 17 THE ASSIGNMENT This programming assignment has two deliverables: 1. A Python program that implements functionality to generate a binary tree, produce a depth first search on its nodes, and plot the resulting tree. This program will be submitted to ZyBooks in ZyLab 18.25. The Pythonscript you write must conform to all requirements listed in the next section. The Zylab problem includes a code template that provides partial implementations for some of the required functions. 2. A short report documenting your program, including an explanation of how you implemented your solution. You will include with this a rendered version of a binary tree produced by your program that matches exactly the formatting in figure 1. The number of nodes in your binary tree will be computed as a function of your Drexel email address, as described in the next section. A PDF version of this report will be submitted via Drexel Learn. Your report must conform to all requirements listed below. PYTHON PROGRAM REQUIREMENTS 1. Your program must define a binaryTree class with the following specifications: 2 4 / 4 100% + Leo REPORT REQUIREMENTS 1. Use a font size no bigger than 12pt and no smaller than 11pt. 2. Use 1-in margins. 3. There is no length requirement or restriction. 4. Explain how you implemented the depth first search. 5. Explain when you invoke the depth first search. 6. Embed a figure showing a rendering of the binary tree with the number of nodes obtained from your my NumberOf Nodes () function. See Figure 1 for an example. 7. Your figure must have a caption. Your figure caption starts with a name, e.g. Figure 1. You should then have a title sentence, indicating what the figure contains. You should then include a few descriptive sentences describing the figure. The last sentence of your figure caption must include your drexel enrail as well as the hash value and computed number of nodes from the my NumberOfNodes function (above). 8. Be sure to refer to the figure from the report text. 9. The report should include your name, lecture section, and lab section near the top. 10. The filename of your report should be of the format: - - Programming-Assignment-2-DFS.pdf 1 Introduction Binary trees are a type of data structure that consists of a list of nodes. Each node may have a parent. Each node may also have two children, called here (left_child, right_child). Nodes without a parent are called root nodes. Nodes without children are called leaf nodes. In the example below, node O is a root node, nodes 4,5,6,7,8 are leaf nodes. One of the main techniques for working with binary trees is to traverse the tree, visiting each node in a specific order. One important algorithm for traversing a binary tree is called depth first search. This is the algorithm you will use for this a ssignment. Depth first search explores as far as possible along the left_child path. When there are no more left children to explore, the algorithm backs out to the right_child and continues exploring. The depth first search algorithm is typically implemented using recursion. For the example tree shown in Figure 1, the depth first search order would be (7,8,3,4,1,5,6,2,0]. Figure 1 X binary tree with 9 nodes 0 generation 2 H 0.0 0.5 1.0 115 2.0 2.5 3.0 3.5 4.0 Figure 1: Example binary tree with 9 nodes. The root node (0) has no parent. The leaf nodes are [4,5,6,7,8). Your submission will produce the same plot formatting, but with the number of nodes computed as specified in the problem specification. Note the alignment on the text nodes (center for root, right aligned for loft_child and Mettalioned forint child the vaxis is invented in that reasonanerations ander down the man with ticks Figure 1: Example binary tree with 9 nodes. The root node (0) has no parent. The leaf nodes are [4,5,6,7,8). Your submission will produce the same plot formatting, but with the number of nodes computed as specified in the problem specification. Note the alignment on the text nodes (center for root, right aligned for left child and left aligned for right_child. The y axis is inverted so that increasing generations render down the page, with ticks draw only at integer generation values. The number of nodes in the binary tree was calculated using the function my NumberOfNodes('me 123@drexel.edu) For this programming assignment, you will develop a Python class that implements the functions and data management associated with binary trees. The programming template contains a list of the class methods and member variables that you must implement. 1 2 3 4 Algorithm 1: Traversing a binary tree with depth first search to set (x,y) render locations for each node. Result: A list of node_ids in depth first search order, with x and y values for each node Initialize the binary tree structure with N nodes, initialize a variable XMAX to store the rightmost leaf node found so far, and call dfs Traverse Initially on the root node. def af e Traverse (node, XMAX=0, y=0) #node has children #traverso left child farat (dfs, XMAX) = dfsTraverse (node.left child, XMAX.child.y) # we get to this line after all our descendents left_children have been processed (dfs, XMAX) - dfsTraverse (node.left_child.XMAX,child-y) #Bet parent node locations stday between children node * = (node.left_child.x+node right_child. 2)/2.0 mode.yey i node has no children bet la location at next integer Vio node.x- XMAX ve increment y at each generation the root in a yo 10 2 72 100% + 7 9 10 11 12 # set parent node locations midway between children node.x = (node.left_child.x+node.right_child.x)/2.0 node.y=y # if node has no children, set leaf location at next integer value node.x = XMAX # we increment y at each generation, so the root is at y=0, its children are at y=1, etc... node.y = y XMAX += 1 # after processing children, add node to dfs list dfs.append (node) return (afs , XMAX) 13 14 15 16 17 THE ASSIGNMENT This programming assignment has two deliverables: 1. A Python program that implements functionality to generate a binary tree, produce a depth first search on its nodes, and plot the resulting tree. This program will be submitted to ZyBooks in ZyLab 18.25. The Pythonscript you write must conform to all requirements listed in the next section. The Zylab problem includes a code template that provides partial implementations for some of the required functions. 2. A short report documenting your program, including an explanation of how you implemented your solution. You will include with this a rendered version of a binary tree produced by your program that matches exactly the formatting in figure 1. The number of nodes in your binary tree will be computed as a function of your Drexel email address, as described in the next section. A PDF version of this report will be submitted via Drexel Learn. Your report must conform to all requirements listed below. PYTHON PROGRAM REQUIREMENTS 1. Your program must define a binaryTree class with the following specifications: 2 4 / 4 100% + Leo REPORT REQUIREMENTS 1. Use a font size no bigger than 12pt and no smaller than 11pt. 2. Use 1-in margins. 3. There is no length requirement or restriction. 4. Explain how you implemented the depth first search. 5. Explain when you invoke the depth first search. 6. Embed a figure showing a rendering of the binary tree with the number of nodes obtained from your my NumberOf Nodes () function. See Figure 1 for an example. 7. Your figure must have a caption. Your figure caption starts with a name, e.g. Figure 1. You should then have a title sentence, indicating what the figure contains. You should then include a few descriptive sentences describing the figure. The last sentence of your figure caption must include your drexel enrail as well as the hash value and computed number of nodes from the my NumberOfNodes function (above). 8. Be sure to refer to the figure from the report text. 9. The report should include your name, lecture section, and lab section near the top. 10. The filename of your report should be of the format: - - Programming-Assignment-2-DFS.pdf