please use python to finish code node.py and tree.py

Maintain a tree where each node in the tree holds a gold value as its key, as well as the property k$\_$sum. The value of the $"$k$\_$sum" is equivalent to the summed gold value of the k highest gold values in the subtree of the node.

Example with k $=1$:$($see picture$1)$

Move Subtree

You must also support the move$\_$subtree$($node$\_$a$,$ node$\_$b$)$ function, where the subtree rooted at node$\_$a is made into a child of node$\_$b$.$ If node$\_$b already has children, your function should make node$\_$a the last child. You must ensure that the k$\_$sum property is correct for all nodes, after moving the subtree. You can assume that node$\_$b isn$$t in the subtree of node$\_$a and you don$$t have to check for this.

Example:$($see picture$1)$

Melt Subtree

Your tree must support the melt$\_$subtree$($node$\_$a$)$ operation. When called, the function removes the subtree rooted at node$\_$a and update the gold value of node$\_$a with the sum of the gold in its $($removed$)$ subtree. You must ensure that the k$\_$sum property is correct for all nodes, after moving the subtree.

Example:$($see picture$2)$

TO IMPLEMENT:

You will need to implement these functions:

node.py

$\_\_$init$\_\_$

add$\_$child

update$\_$gold

return$\_$k$\_$sum

tree.py

put

move$\_$subtree

melt$\_$subtree

$($Note$,$ you can add additional functions and variables to the classes as you see fit, so feel free to modify and extend those as long as you leave the existing function signatures and variables intact.$)$

Code:

Node.py:

class Node$()$:

# These are the defined properties as described above

children: list$[\text{'}$Node$\text{'}]$

parent: 'Node'

gold: int

k$\_$sum: int

k: int

def $\_\_$init$\_\_($self$,$ gold: int, k: int$)->$ None:

$"""$

The constructor for the Node class.

:param gold: The gold of the node.

:param k: Value used to calculate k$\_$sum.

$"""$

# TODO Initialize the properties of the node

def add$\_$child$($self$,$ node: 'Node'$)->$ None:

$"""$

Adds the given node as a child of the current node.

The given node is guaranteed to be new and not a child of any other node.

:param node: The node to add as the child

$"""$

# TODO Add the given node as the right child of the current node

def is$\_$external$($self$)->$ bool:

$"""$

Returns True if the node is a leaf node.

:return: True if the node is a leaf node.

$"""$

return len$($self$.$children$)==0$

def update$\_$gold$($self$,$ gold: int$)->$ None:

$"""$

Updates the gold of the current node.

:param gold: The new gold of the node.

$"""$

# TODO Update the gold of the node

def get$\_$children$($self$)->$ list$[\text{'}$Node$\text{'}]$:

$"""$

Returns the children of the current node.

:return: The children of the current node.

$"""$

return self.children

def return$\_$k$\_$sum$($self$)->$ int:

$"""$

Returns the k$\_$sum of the current node.

:return: The k$\_$sum of the current node.

$"""$

# TODO Return the k$\_$sum of the node

$-----------------------------------$

Tree.py

from Node import Node

class Tree$()$:

# These are the defined properties as described above

root: Node

def $\_\_$init$\_\_($self$,$ root: Node $=$ None$)->$ None:

$"""$

The constructor for the Tree class.

:param root: The root node of the Tree.

$"""$

self.root $=$ root

def put$($self$,$ node$\_$a: Node, node$\_$b: Node$)->$ None:

$"""$

Adds node$\_$b as the last child of node$\_$a$.$

You are guranteed that the given node is not already part of the tree

:param node$\_$a: The node to add the child to$.$

:param node$\_$b: The child to add to the node.

$"""$

# TODO Add the child to the node

def move$\_$subtree$($self$,$ node$\_$a: Node, node$\_$b: Node$)->$ None:

$"""$

The subtree rooted at node$\_$a is made into a child of node$\_$b$.$

If node$\_$b already has children, your function should make node$\_$a the last child.

You must ensure that the k$\_$sum property is correct for all nodes, after moving the subtree.

You can assume that node$\_$b isn't in the subtree of node$\_$a and you don't have to check for this.

:param node$\_$a: The root of the subtree to move.

:param node$\_$b: The node to add the subtree to$.$

$"""$

# TODO Move the subtree rooted at node$\_$a to the last child of node$\_$b

def melt$\_$subtree$($self$,$ node$\_$a$)->$ None:

$"""$

Removes the subtree rooted at node$\_$a and updates the gold value of node$\_$a with the sum of the gold in its $($removed$)$ subtree.

You must ensure that the k$\_$sum property is correct for all nodes, after removing the subtree and updating the gold value.

$"""$

# TODO Remove the subtree, update the gold value of node$\_$a and update k$\_$sum values