Unordered tree

I have to create two classes [login to view URL] that supports the following functions: - init (self): supports the following properties -root: Node - add_child(self, u: Node): Adds a new node to the tree as a child of the given node. The new node should have the next sequential id in the tree; that is, if you have n nodes in the tree, the new node should have id n+1. You are guaranteed that the given node is not already part of the tree. u: node to add a new child to. - min_pre_order_rank(self, u: Node): Finds the minimum pre-order rank of the given node. That is the lowest possible index in a pre-order traversal - attach((self, T: "Tree", u: Node): Attaches the given tree as a child to the given node, merging the two trees.T = tree to attach, u: = node to attach the tree to - pre_order(self, master_order: List[int]: Return the pre-order traversal of the tree given a master order. and [login to view URL]: which supports the following functions: - init(self, id: int) supports the following properties id: int children: List["Node"] parent: "Node" - add_child(self, u: "Node"): Adds the given node as a child of the current node. The given node is guaranteed to not be a child of any other node. - get_children(self): returns the children of the current node - get_parent(self): returns the parent of the current node - set_parent(self, u: "Node"): Sets the parent of the current node. u: = parent node Problem: Let T be an unordered tree (not necessarily binary) on n district integers keys. Because T is unordered, there can be multiple pre-order traversals (depending on how we iterate over the children of each node). ​ Example: in the tree ​ 1 / | \ / | \ 3 2 4 | | 5 two possible pre-order traversals could be: [1, 4, 3, 5, 2] (if we iterate over the children of 1 in [4, 3, 2]-order) or [1, 3, 5, 4, 2] (if we iterate over the children of 1 in [3, 4, 2]-order). Note, however, that if we were given a master order of all the nodes in the tree and we scanned the children of each node following this master order, then the pre-order traversal is uniquely defined by this master order. Example: in the tree ​ 1 / | \ / | \ 3 2 4 / \ / \ 5 6 [1, 2, 5, 6, 3, 4] is the pre-order traversal defined by the master order [5, 2, 3, 6, 4, 1], while [1, 4, 3, 2, 6, 5] is the pre-order traversal defined by the master order [6, 4, 3, 1, 2, 5]. For a given tree T and a master order M, we say that the pre-order M-rank of node x is k, if x is the kth node in the pre-order traversal defined by M.