Implement a pre-order traversal on a Linked Binary Tree in PYTHON A pre-order traversal of a tree is a traversal which visits the current node before traversing any of its children. In pseudocode, a recursive pre-order traversal of a binary tree looks like this: preorderTraversal(p): visit(p) preorderTraversal(tree.left(p)) preorderTraversal(tree.right(p)) Your task is to implement a method which carries out a pre-order traversal of a tree, and builds and returns a list of the elements in the tree in the order in which they were encountered by the traversal. You need to implement the preorderTraversal() method in the LinkedBinaryTree class. In both programming languages, there is an empty main function in the Linked Binary Tree file. The main function is not being tested and it is there as an option for you to use for your own testing / running. skeleton: import core class Node(core.Position): def __init__(self, element, parent=None, left=None, right=None): self.element = element self.parent = parent self.left = left self.right = right def get_element(self): return self.element class LinkedBinaryTree(core.BinaryTree): def __init__(self): # The number of nodes in the tree self._size = 0 # The root of the tree self._root = None def size(self): return self._size def is_empty(self): return self._size == 0 def left(self, p): return p.left def right(self, p): return p.right def sibling(self, p): parent = p.parent if parent is None: return None if parent.left == p: return parent.right return parent.left def root(self): return self._root def parent(self, p): return p.parent def num_children(self, p): result = 0 if p.left is not None: result += 1 if p.right is not None: result += 1 return result def is_internal(self, p): return self.num_children(p) > 0 def is_external(self, p): return self.num_children(p) == 0 def is_root(self, p): return self._root == p def add_root(self, e): """Adds a root with element e to an empty tree.""" if not self.is_empty(): raise ValueError("Cannot add root to non-empty tree") self._root = Node(e) self._size = 1 return self._root def add_left(self, p, e): """Adds a new left child of Position p storing the element e, returning the new position. It raises an exception if p already has a left child.""" if p.left is not None: raise ValueError("Cannot add left to position with a left child") child = Node(element=e, parent=p) p.left = child self._size += 1 return child def add_right(self, p, e): """Adds a new right child of Position p storing the element e, returning the new position. It raises an exception if p already has a right child.""" if p.right is not None: raise ValueError("Cannot add right to position with a right child") child = Node(element=e, parent=p) p.right = child self._size += 1 return child def set_element(self, p, e): """Replaces the element with e at the given Position p and returns the replaced element.""" old_element = p.element p.element = e return old_element def remove(self, p): """Removes the node at Position p and replaces it with its child, if any, and returns the removed element. Raises an exception if p has two children.""" if self.num_children(p) == 2: raise ValueError("Cannot remove a node with two children") child = p.left if child is None: child = p.right if child is not None: child.parent = p.parent if self.is_root(p): self._root = child elif p == p.parent.left: p.parent.left = child else: p.parent.right = child self._size -= 1 return p.element def attach(self, p, left_tree, right_tree): """Attaches left_tree and right_tree to the left and right of the leaf p. Left_tree and right_tree are set to empty on completion. Raises an exception if p is not a leaf.""" if self.is_internal(p): raise ValueError("p must be a leaf") self._size += left_tree.size() + right_tree.size() if not left_tree.is_empty(): left_tree.root().parent = p p.left = left_tree.root() left_tree._root = None left_tree._size = 0 if not right_tree.is_empty(): right_tree.root().parent = p p.right = right_tree.root() right_tree._root = None right_tree._size = 0 def preorder_traversal(self): """Returns a list of elements in the tree in an order corresponding to the order in which they would be visited in a pre-order tree traversal.""" elements = [] # TODO: Implement this. return elements def main(): # This function is here for you to optionally use for your own # testing / running. This function will NOT be tested. pass if __name__ == "__main__": main()