Write a program that implements a binary search tree using a node-pointer implementation. Assume all entries in the tree will be unique. struct node { int data; node * left; node * right; }; Requirements: 1) Implement the following functions: a) void insert(int data) // creates a new node and inserts it in the correct location in the tree b) void print_preorder(node * root); // prints the data in a tree using a preorder traversal c) void print_postorder(node * root); // prints the data in a tree using a postorder traversal d) void print_inorder(node * root); // prints the data in a tree using an inorder traversal e) int search(int data) // searches the tree for data. Returns 0 if data is not found, otherwise, returns the number of nodes visited MUST RUN IN O(logN) time!!!!!! 2) Insert the following sequence into the tree: Sequence A: 1,5,4,6,7,2,3 Sequence B: You could cut and paste this sequence into your source code and create a hard-initialized array. The sequence is also posted in a txt file. 150,125,175,166,163,123,108,116,117,184,165,137,141,111,138,122,109,194,143,183,178,173,139,126,170,1 90,140,188,120,195,113,104,193,181,185,198,103,182,136,115,191,144,145,155,153,151,112,129,199,135,14 6,157,176,159,196,121,105,131,154,107,110,158,187,134,132,179,133,102,172,106,177,171,156,168,161,149 ,124,189,167,174,147,148,197,160,130,164,152,142,162,118,186,169,127,114,192,180,101,119,128,100 3) Search the Sequence A tree for values 1, 4, 2, and print the return values. 4) Search the Sequence B tree for values 42, 142, 102, 190, and print the return values. 5) Traverse the tree with each of the three traversal functions above, and print the sequence of output for each of the traversals. 6) DRAW the tree for Sequence A only, showing the path of traversal and the sequence of processing for each of the three given traversals. That is, indicate on the path where the processing of each node occurs. 7) State the time complexity for each of the functions in part 1 and explain your answers. Turn in: 1) Paper source code listings. 2) Paper output listings demonstrating all program functionality. Use the insertion sequence provided. Perform all three traversals and include the output from each one. 3) A diagram for each of the three traversals for sequence A only. 4) Your Big O’s for each function. Documentation standards: Follow format guidelines in syllabus.