class Stack: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def push(self, item): print("New node on stack") self.items.append(item) def pop(self): if self.is_empty(): raise IndexError('ERROR: The stack is empty!') return self.items.pop() def peek(self): if self.is_empty(): raise IndexError('ERROR: The stack is empty!') return self.items[len(self.items) - 1] def size(self): return len(self.items) def __str__(self): return str(self.items)[:-1] + '

class BinaryTree: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right

def insert_left(self, new_data): if self.left == None: self.left = BinaryTree(new_data) else: t = BinaryTree(new_data, left=self.left) self.left = t

def insert_right(self, new_data): if self.right == None: self.right = BinaryTree(new_data) else: t = BinaryTree(new_data, right=self.right) self.right = t

def get_left(self): return self.left

def get_right(self): return self.right

def set_data(self, data): self.data = data

def get_data(self): return self.data

def set_left(self, left): self.left = left

def set_right(self, right): self.right = right

#insert the __iter__(self) method here class BTPreorderIterator: def __init__(self, tree): def __next__(self):

In the answer box is a class BinaryTree as discussed in the lecture. Define an iterator called BTPreorderIterator (binary_tree) which is initialised with the root of a binary tree and iterates through the tree in Preorder. Your implementation should contain the methods __ init () and __ next () Please add a method __iter ( )_ to the BinaryTree class which returns the Preorder iterator. IMPORTANT: The function must be efficient, i.e., do not access nodes unnecessarily. You can achieve this by using a stack. Note: You can assume that the parameter binary tree is not empty. Note: A stack implementation is provided to you in the answer box. The push () method prints out a message if you add a value to the stack. This is used to check that you only traverse the part of the tree required for the iterator. HINT: The init () method should initialise the stack with the root of the binary tree. The next () method should return the top element of the stack (if stack is not empty) and check whether the left and right child of the current node exist and if yes, put them on the stack. This will enable the iterator to return the correct node if next ( ) is called again. Think about in what order you need to put the children of a node onto the stack data structure and when you need to raise a StopIteration. Example: The first three examples below show the output for a tree with four nodes: For example