PART 1 GENERAL TREES In this part you will be implementing a general tree data structure where each node of a tree can have any number of children nodes. Refer to tree.hpp which provides all the required definitions. Write your implementation in tree.cpp using the boiler code. Member Functions": Write implementation for the following methods as described here: Tree(shared_ptr_node> root) Constructor shared_ptr> findKey(T key) Finds the node with the given key and returns a pointer to that node. NULL is returned if the key doesn't exist. shared_ptr> findKeyHelper (shared_ptr curr Node, T key) Helper function to be used in findkey(T key) function bool insertChild(shared_ptrenode> newNode, T key) Inserts the given node as the child of the given key. Returns true if insertion is successful and false if key doesn't exist. Insertion should also fail if another node with the same key as the new node already exists i.e. duplicates are not allowed. If the node at the given key already has children, the new node must be added to the tail of the children of that node. vector>>getAllChildren(T key) Returns all the children of the node with the given key. Should return an empty vector in case the node has no child or key doesn't exist. int findHeight() Returns the height of the tree int findHeightHelper (shared_ptr> currNode) In this assignment, you are free to declare any helper functions as per your need but the already declared function declarations should not be modified. Helper function to be used in the findHeight() function void delete Tree(shared_ptr> currNode) Delete the entire tree. bool deleteLeaf (T key) Delete node with given keyif and only if it is a leaf node i.e. have no child. Doesn't delete the root node even if it is the only node in the tree. Returns true on success, false on failure. shared_ptr> deleteLeafHelper (shared_ptr> currNode, I key) Helper function to delete the leaf node