This week, we start to implement the Binary Search Tree $($BST$).$

In this Binary Search Tree, we consider nodes that contain a key of type int. The first step is to implement a class BSTNode. In this class, create the following

elements:

$$ Constructor by default $($no input$)$

$$ Constructor that specifies the value of a key

$$ Destructor $($it does nothing$)$

$$ Function that determines if the node is a leaf or not.

$$ Function that returns the number of children.

Create a function that returns the parent of a node child.

$$ BSTNode$*$ Parent$($BSTNode$*$ root,BSTNode$*$ child$)$;

Create a function to search if an element is present in the tree.

Create a function to insert an element in the tree.

$$ bool SearchNodeREC$($BSTNode$*$ root, int data$)$; $//$ Recursive version

$$ bool SearchNodeITE$($BSTNode$*$ root, int data$)$; $//$ Iterative version

$$ void InsertNodeREC$($BSTNode$**$ root, int data$)$; $//$ Recursive version

$$ void InsertNodeITE$($BSTNode$**$ root, int data$)$; $//$ Iterative version

For each function, start by implementing the base case, and then the recursive calls.