Instructions:

Implement a binary tree with the following features:

Define the structure Node for a tree:

c

Copy code

typedef struct Node $\{$

int data;

struct Node$*$ left;

struct Node$*$ right;

$\}$ Node;

a$)$ Implement a function Node$*$ createNode$($int data$)$ that creates a new node with the given data and returns its pointer.

b$)$ Implement a function Node$*$ insertNode$($Node$*$ tree, int data$)$ that correctly inserts a node with the given data into the tree. This function should also call createNode to create the node.

c$)$ Implement a function called Node$*$ deleteNode$($Node$*$ tree, int data$)$ that correctly deletes a node from the tree. Do not balance the tree after deletion.

d$)$ Create a void inOrderTraversal $($Node$*$ tree$)$ function that traverses the tree in$-$order and prints the elements post order.

e$)$ Create a void preOrderTraversal $($Node$*$ tree$)$ function that traverses the tree pre$-$order and prints the elements pre$-$order.

f$)$ Create a void postOrderTraversal $($Node$*$ tree$)$ function that traverses the tree post$-$order and prints the elements post$-$order.

g$)$ Write a function int calculateHeight $($Node$*$ tree$)$ to calculate the height of the binary tree.

h$)$ Write a function int nodeCount $($Node$*$ tree$)$ to count the total number of nodes in the tree.

i$)$ Implement a search function int search $($Node$*$ tree, int value$)$ that checks if a value is in the tree.

j$)$ Create a function int minimum$($Node$*$ tree$)$ to find the minimum value in the tree.

k$)$ Create a function int maximum$($Node$*$ tree$)$ to find the maximum value in the tree.

Write a main$()$ function to test your implemented functions. Create a tree by inserting nodes using the insertNode$()$ function and perform the following operations:

a$)$ Insert at least seven nodes with integer values of your choice.

b$)$ Print the tree list using inOrderTraversal, preOrderTraversal, and postOrderTraversal$().$

c$)$ Call the calculateHeight$()$ and nodeCount$()$ functions and display the height and node count of the tree.

d$)$ Call the deleteNode$()$ on the minimum number, the maximum number, and the middle number, and inOrderTraversal$()$ after each deletion to display the result of the deletions.

e$)$ Call the search$()$ function on an item that does not exist in the tree.

Perform a Big O analysis of all the functions, except the main$()$ function. Explain clearly and precisely how you calculated the Big O$.$