Using the implementation of a binary tree node class named bt_node provided for you below, you will implement a number of methods for a class called complete_binary_tree , which represents a complete binary tree. You must know what a complete binary tree is, since we covered this topic in lectures. You will need to either complete or provide the implementation for the following set of static and instance methods for the complete_binary_tree class: Static methods: count_nodes ( root ) returns the number of nodes in the binary tree, whose root is root. .tostring( root, level=0, indent=' ") returns a string representation of the binary tree that starts at the root node in a special format. Each level of the tree must be indented by level times four spaces. The indent value specifies these four spaces already as a default parameter. Therefore, since the root node resides at level 0, there will be no indent for printing the root node. After requisite number of indentation, your function should place the value of the node in question, followed only by an end-of-line ( ) character. No other extra spaces or characters should be added. Otherwise, your results will look wrong to the testing code. Simply follow these specifications. In addition, this method should return a string such that the root node is in the middle with the left subtree below the root and the right subtree above the root. For example, the binary tree represented pictorally as 100 1 / 84 60 23 12 29 should be printed out as follows when the string returned by __str_0 is printed using the print_formatted_string() function provided to you above. The print_formatted_function() prints characters with alternating background colors so that one can easily tell where each string ends and how many spaces are used. Note that each line of the printout ends in an end-of-line character! Also note how the right subtree that starts with node 71 is printed on top, as should be the case. This way, you can confirm that the shape of the above tree is reflected in the output if you tilt your head to the left while looking at this output. . is_completel root ) returns True if the provided binary tree that starts at root-an instance of complete_binary_tree is a complete binary tree. Otherwise, this method should return False. When there are no nodes in the binary tree, this method should return False. This function must be implemented using ITERATION, not recursion! Instance methods: init ( self, root=None ) should initialize a complete binary tree. In default mode, this method will create an empty tree. If an already built tree is passed into root, then this method will initialize the binary from the root. The root node of the tree must be kept in an instance variable named root. Note tha this instance variable has already been defined for you. . insert( self, value ) inserts a new bt_node with the provided value such that the binary tree is always complete shape-wise. . len( self ) returns the number of nodes in the binary tree. _equ( self, other ) returns True if this tree and the other are shape-wise and value-wise equal. Otherwise, it should return false. You may want to implement this using a static function that works recursively. This means, value must be in exactly the same location in both trees, in order for those two trees to be considered equal. _str_( self ) returns a string representation of the binary tree in a special formatSee the description of tostring(). These two methods are functionally equivalent. See the details of how the returned string should be constructed in the description of the tostring() method above. repr (self) returns what _str() returns Additional Specifications and Suggestions . You must develop your solution from scratch! That means, you are not allowed to use any import statements other than that that imports defaultdict and bt_node in your implementation. These import statements have already been included in the code cell where you need to write your answer. Your implementation absolutely needs the definition of the bt_node class. You may you wish to use the defaultdict class, which you are perfectly allowed to do. Even if your code uses a single import statement other than these allowed ones, you will receive zero automatically for this entire test! Failure to follow specifications is a major flaw on the part of an engineer, and, therefore, no excuses will be accepted, even if your existing code with disallowed import statements works perfectly! That is, it will not matter at all whether your code works given that you disregarded and violated provided specifications. In other words, anything that works is and will not be accepted! This test is not about you providing anything that works. It is about providing a correct solution, given these specifications. Your code will be tested automatically and whether you have used disallowed import statements will also be checked automatically . Do what seems easiest first. Otherwise, you may run out of time if you spend a lot of time on more difficult parts of this question. If you first work on the easier methods, at least, you will have some of the functions implemented and tested so that you can get some points. The most difficult methods to write are insert() and is complete (). Plan accordingly and use your time wisely. No time extension will be provided. Please do not ask for it. So do as much as you can within the 3 hours you have. . You may want to work elsewhere, such as using GVIM, where you can type faster and be more efficient. Then, once you make sure your code works, you can transfer it and run the tests, after already running them separately to make sure you on the right track. Since this notebook is relatively long, it may be easier for you to work like this. This is purely a suggestion. The code snippets provided to you below should give you hints on how you may implement the rest of a given method or another method altogether. Be smart and take advantage of these hints. Set your alarm clock to go off to warn you 30 minutes, 10 minutes, and 5 minutes before end of the exam so that you can pace yourself. Time yourself according to the time kept by UZEM. Do not wait for the last second to upload your file. No extension will be provided for uploading files. If you fail to upload your file, your case will be treated as if you did not take this exam. WARNING If you write these functions disregarding the strict specifications mentioned above, you will not get any credit for your solutions, even if they happen to "work." Once again, I hope that you decide to work HONESTLY. If you fail to do so, the consequences will unfortunately be harsh. RUN THE FOLLOWING CODE CELL CREATE THE FILE bt_node.py 44 file bt_node.py class bt_node: 11 I IT Defines a node in the binary tree II III def init__( self, value, left=None, right=None ): TFT self.value self.left self.right value left right def e_(self, other ): def init self, value, left=None, right=None ): TETT T111 self.value = value self.left = left self.right right def eq_(self, other ): Returns True if this and the other node has the identical value. If the other node is None, this method returns False, since no equality check can actually be performed. return false if other is None else self.value other.value def _it__( self, other ): To enable sorting return self.value