Using the template thats given, fill in the python code while following the given guidelines in order to output a binary tree similar to the one shown. Be sure to include a function at global scale that maps an email address to the number of nodes in the plot.

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 binary tree with 9 nodes 0 1 generation 2 0.0 0.5 1.0 1.5 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 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 myNumberOfNodes('me123@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 5 6 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 dfs Traverse (node , XMAX=0, y=0): # if node has children # traverse left child first (dfs, XMAX) = df sTraverse (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) # 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 14 XMAX += 1 # after processing children, add node to dfs list dfs.append(node) return (dfs, XMAX) 7 8 9 10 11 12 13 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 binary Tree class with the following specifications: PYTHON PROGRAM REQUIREMENTS 1. Your program must define a binaryTree class with the following specifications: 2 (a) Your binaryTree class must have as data attributes a dictionary called nodeChildren that maps a node to its (left_child, right_child) nodes, a dictionary called nodeParent that maps a node to its parent node, and a dictionary called treeXY that maps a node to its (x,y) location. (b) Your binaryTree class must have a method called addTrio (parent, left_child, right_child ) that adds a new pair of nodes (left_child, right_child) to the tree. If parent is the root then parent is added to the tree as well. (c) Your binaryTree class must have a method called leaves that returns a list of all leaf nodes in the tree and a method called nodes that returns a list of all nodes in the tree. (d) Your binaryTree class must have a method called addNodes (nNodes) adds at most nNodes to the tree. For example, calling addNodes (18) on an empty tree would result in a tree with 17 nodes. Why does the number of nodes have to be odd? Calling addNodes (nNodes) on a non-empty tree adds nNodes additional nodes to the tree. (e) Your binaryTree class must have a method called df sTraverse that returns a depth first search ordered list of nodes in the tree. See Figure 1 and the code template in zybooks for more detail. (1) Your binaryTree class must have a method called render that produces a plot of a binary tree with the number of nodes determined as described below. The leaf nodes are placed at integer locations in increasing order of their discovery by the depth first search. Parent nodes are set midway between each leaf node. Each node should have a vertical line extending from their node.y to node.y+1. Node labels should be printed at their (x,y) location, with left_child nodes right aligned, and right_child nodes left aligned. The root text label should be centered. 2. Your program must include a function at global scope called myNumberOf Nodes that maps your drexel email address to the number of nodes in the plot that you will submit. def my NumberOfNodes (email Address): # pass your email address (you123@drexel.edu) as the parameter hash=0 forcin email Address: hash += ord (c) return 17+hash%15 Be sure to put your own Drexel email in for the email Address parameter. 1 2 class binaryTree: def _init__(self, nNodes=(): # Initialize tree structures, build default tree pass def addTrio(self, parent, leftChild, rightChild): # add leftChild, rightChild to tree pass def setRoots(self): # for this problem set, there is a single root nade. sometimes trees can # have multiple roots though, so we keep that option here. 7 self.roots=[1 for p in self.nodes(): if p not in self.nodeParent.keys(): pass def dfsTraverseRecursive(self, node,dfsNodeList, xMaxLeaf=8, yNode=0): # traverse the tree using dfs. set x and y location as we go. # find my children if node in self.nodeChildren.keys(): (cLeft, cRight)=self.nodeChildren (node] # traverse left child (dfsNodeList,xMaxLeaf)=self.dfsTraverseRecursive (cLeft, dfsNodeList,xMaxLeaf,yNode+1) # traverse right child pass # after we're done with both children, set parent x midway between children x location. # what do we set for parent y? # self. treexy Inode] =(7,7) pass else: # node has no children. It's a leaf. set it's x self.treeXY (node)=(xMaxLeaf, yNode) # increment xMaxLeaf so next leaf goes exactly 1 to the right of me pass # nade's children are done, now add node to the dfsNodelist pass return (dfsNodeList,xMaxLeaf) def nodes(self): # return the set of all nodes in the tree nodes=set (self.nodechildren.keys()) .union(set (self.nodeParent.keys())) # note - if the tree is empty, return a single root node {0} pass return nodes pass return nodes def leaves(self): # return the set of all leaves in the tree # a node is a leaf if it's not in self.nodeChildren.keys(): leaves=set() pass return leaves def dfsTraverse(self): self.setRoots() dfs=1 each root node will be processed to append its dfs traversal to the dfs list # here we will only test / use trees with a single root for r in self.roots: dfs=self.dfsTraverseRecursive(r,dfs) return dfs def render(self, node): # render node xy=self.treeXY (node) # all plotting with defaults unless otherwise specified # plot a vertical blue solid line at node.x from node.y to node.y+1 pass # text align right for child , teft for child 1 if node in self.nodeParent.keys(): #p is node's parent p=self.nodeParent (node) # ex are node's parent's two children. node should be one of them. cx=self.nodeChildren (pl # if node is the left child, align right # else align left else: # no parent - node is the root align='center' plt.text(xy(0),xy(1),str(node), horizontalalignment-align) # if node has children, draw a horizontal line in solid blue # between the two children x locations, at the children y location if node in self.nodeChildren.keys(): # plot horizontal pass # now render the left child then the right child #self. render(leftChild) #self.render(rightChild) # self.render(leftChild) # self.render rightChild) def addNodes(self, nNodes): # add nNodes new nodes to the tree n@=len(self.nodes()) # current nodes in tree nNodes=nNodes+no # target tree size while len(self.nodes()) +2c=nNodes: for 1 in self.leaves(): if len(self.nodes() )+2>nNodes: break mm=max(self.nodes) self.addTrio(2, mm+1, mm+2) # after we add new nodes to the tree, we reset everyone's xy locations # by invoking a dfsTraverse self.dfsTraverse() def myNumberOfNodes (emailAddress): # see the bblearn problem statement pass if name_="_main_": # test your code here pass # generate your plot here # you'll need to use matplotlib invert y axis so plot goes the right direction # set the title correctly as in the sample plot. # set the yticks, ylabel, xticks and xlabel too # use ctrl+print screen to copy the matplotlib figure window, then paste it into word (or use latex if you like) for your report. be sure to write your figure # caption carefully and follow all instructions #plt... #plt.show() pass 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 binary tree with 9 nodes 0 1 generation 2 0.0 0.5 1.0 1.5 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 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 myNumberOfNodes('me123@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 5 6 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 dfs Traverse (node , XMAX=0, y=0): # if node has children # traverse left child first (dfs, XMAX) = df sTraverse (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) # 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 14 XMAX += 1 # after processing children, add node to dfs list dfs.append(node) return (dfs, XMAX) 7 8 9 10 11 12 13 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 binary Tree class with the following specifications: PYTHON PROGRAM REQUIREMENTS 1. Your program must define a binaryTree class with the following specifications: 2 (a) Your binaryTree class must have as data attributes a dictionary called nodeChildren that maps a node to its (left_child, right_child) nodes, a dictionary called nodeParent that maps a node to its parent node, and a dictionary called treeXY that maps a node to its (x,y) location. (b) Your binaryTree class must have a method called addTrio (parent, left_child, right_child ) that adds a new pair of nodes (left_child, right_child) to the tree. If parent is the root then parent is added to the tree as well. (c) Your binaryTree class must have a method called leaves that returns a list of all leaf nodes in the tree and a method called nodes that returns a list of all nodes in the tree. (d) Your binaryTree class must have a method called addNodes (nNodes) adds at most nNodes to the tree. For example, calling addNodes (18) on an empty tree would result in a tree with 17 nodes. Why does the number of nodes have to be odd? Calling addNodes (nNodes) on a non-empty tree adds nNodes additional nodes to the tree. (e) Your binaryTree class must have a method called df sTraverse that returns a depth first search ordered list of nodes in the tree. See Figure 1 and the code template in zybooks for more detail. (1) Your binaryTree class must have a method called render that produces a plot of a binary tree with the number of nodes determined as described below. The leaf nodes are placed at integer locations in increasing order of their discovery by the depth first search. Parent nodes are set midway between each leaf node. Each node should have a vertical line extending from their node.y to node.y+1. Node labels should be printed at their (x,y) location, with left_child nodes right aligned, and right_child nodes left aligned. The root text label should be centered. 2. Your program must include a function at global scope called myNumberOf Nodes that maps your drexel email address to the number of nodes in the plot that you will submit. def my NumberOfNodes (email Address): # pass your email address (you123@drexel.edu) as the parameter hash=0 forcin email Address: hash += ord (c) return 17+hash%15 Be sure to put your own Drexel email in for the email Address parameter. 1 2 class binaryTree: def _init__(self, nNodes=(): # Initialize tree structures, build default tree pass def addTrio(self, parent, leftChild, rightChild): # add leftChild, rightChild to tree pass def setRoots(self): # for this problem set, there is a single root nade. sometimes trees can # have multiple roots though, so we keep that option here. 7 self.roots=[1 for p in self.nodes(): if p not in self.nodeParent.keys(): pass def dfsTraverseRecursive(self, node,dfsNodeList, xMaxLeaf=8, yNode=0): # traverse the tree using dfs. set x and y location as we go. # find my children if node in self.nodeChildren.keys(): (cLeft, cRight)=self.nodeChildren (node] # traverse left child (dfsNodeList,xMaxLeaf)=self.dfsTraverseRecursive (cLeft, dfsNodeList,xMaxLeaf,yNode+1) # traverse right child pass # after we're done with both children, set parent x midway between children x location. # what do we set for parent y? # self. treexy Inode] =(7,7) pass else: # node has no children. It's a leaf. set it's x self.treeXY (node)=(xMaxLeaf, yNode) # increment xMaxLeaf so next leaf goes exactly 1 to the right of me pass # nade's children are done, now add node to the dfsNodelist pass return (dfsNodeList,xMaxLeaf) def nodes(self): # return the set of all nodes in the tree nodes=set (self.nodechildren.keys()) .union(set (self.nodeParent.keys())) # note - if the tree is empty, return a single root node {0} pass return nodes pass return nodes def leaves(self): # return the set of all leaves in the tree # a node is a leaf if it's not in self.nodeChildren.keys(): leaves=set() pass return leaves def dfsTraverse(self): self.setRoots() dfs=1 each root node will be processed to append its dfs traversal to the dfs list # here we will only test / use trees with a single root for r in self.roots: dfs=self.dfsTraverseRecursive(r,dfs) return dfs def render(self, node): # render node xy=self.treeXY (node) # all plotting with defaults unless otherwise specified # plot a vertical blue solid line at node.x from node.y to node.y+1 pass # text align right for child , teft for child 1 if node in self.nodeParent.keys(): #p is node's parent p=self.nodeParent (node) # ex are node's parent's two children. node should be one of them. cx=self.nodeChildren (pl # if node is the left child, align right # else align left else: # no parent - node is the root align='center' plt.text(xy(0),xy(1),str(node), horizontalalignment-align) # if node has children, draw a horizontal line in solid blue # between the two children x locations, at the children y location if node in self.nodeChildren.keys(): # plot horizontal pass # now render the left child then the right child #self. render(leftChild) #self.render(rightChild) # self.render(leftChild) # self.render rightChild) def addNodes(self, nNodes): # add nNodes new nodes to the tree n@=len(self.nodes()) # current nodes in tree nNodes=nNodes+no # target tree size while len(self.nodes()) +2c=nNodes: for 1 in self.leaves(): if len(self.nodes() )+2>nNodes: break mm=max(self.nodes) self.addTrio(2, mm+1, mm+2) # after we add new nodes to the tree, we reset everyone's xy locations # by invoking a dfsTraverse self.dfsTraverse() def myNumberOfNodes (emailAddress): # see the bblearn problem statement pass if name_="_main_": # test your code here pass # generate your plot here # you'll need to use matplotlib invert y axis so plot goes the right direction # set the title correctly as in the sample plot. # set the yticks, ylabel, xticks and xlabel too # use ctrl+print screen to copy the matplotlib figure window, then paste it into word (or use latex if you like) for your report. be sure to write your figure # caption carefully and follow all instructions #plt... #plt.show() pass