Python. need urgent

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_treeclass:

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 | .-------+-------. / \ 84 71 | | .---+---. .---+---. / \ / \ 60 23 12 29 

  should be printed out as follows when the string returned by __str__() 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.

 29 71 12 100 23 84 60 

• is_complete( root ) returns True if the provided binary tree that starts at rootan instance of complete_binary_treeis 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.

• __eq__( 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, a 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.

• Failure to see or comprehend these specifications cannot be used as excuse to ask for reevaluation for code that clearly violates specifications! Such an attitude will not be tolerated.

• 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.

RUN THE FOLLOWING CODE CELL CREATE THE FILE bt_node.py %%file bt_node.py class bt_node: Defines a node in the binary tree def _init_l self, value, left=None, right=None ): self.value = value self. left = left self.right = right def Leq__( 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 _lt_( self, other ): To enable sorting return self.value