Given the following struct that represents a binary tree: st…

Given the following struct that represents a binary tree: struct Node { int key; Node *parent; Node *left; Node *right; Node(int k) : key(k), parent(nullptr), left(nullptr), right(nullptr){}; }; Write a recursive function that inserts a node in a binary search tree stored using the above structure. If the node passed in is a null pointer, then create the root node. Otherwise, add the node  to the binary search tree. You can assume no equal keys will be added to the binary search tree and return the node that was originally passed to the function.   Use the below function signature (NOTE: this is not a class method) Node *addToBST(Node *node, int k)    

Given this array based binary tree starting at index 0. Answ…

Given this array based binary tree starting at index 0. Answer the following questions. The value refers to the integer within the cell and the index refers to the location of that cell in the array.   66 58 15 87 98 40 62 99 26 31 13 65 30 83 46   5a (1.5 Points): What is the index of the parent of the value 83?       5b (1.5 Points): What is the value of the left child of index 4?       5c (1.5 Points): What is the value of the parent of the value 30?       5d (1.5 Points): What is the index of the right child of index 1?       5e (1.5 Points): What is the value of the grandparent (parent of the parent) of index 11?       5f (1.5 Points): What is the value of the left child of index 12?       5g (1 point): What is the height of this binary tree? (Hint: Root is 0)