Implement the following functions in C++ on a Binary search Tree.

- Insert element: The item will be inserted at the correct position in the Binary search Tree so that the order is maintained.

- Pre-order traversal: perform a pre-order traversal starting at the root node.

- In-order traversal: perform a in-order traversal starting at the root node.

- Post-order traversal: perform a post-order traversal starting at the root node.

Write a C++ program to test the functionality:

- You will start with a empty Tree and create nodes to add the following items:

1, 4, 7, 13 , 25, 37, 41, 75, 83, 109

1. Insert the items in a particular order such that the resulting Binary Tree will be a balanced binary search tree (AVL Tree) and print the order of insertion to the screen (40 points).

2.. Print the pre-order traversal (20 points)

3. Print the in-order traversal (20 points)

4. Print the post-order traversal (20 points)

Project description: Implement the following functions in C++ on a Binary search Tree. - Insert element: The item will be inserted at the correct position in the Binary search Tree so that the order is maintained. - Pre-order traversal: perform a pre-order traversal starting at the root node. - In-order traversal: perform a in-order traversal starting at the root node. - Post-order traversal: perform a post-order traversal starting at the root node. Write a C++ program to test the functionality: - You will start with a empty Tree and create nodes to add the following items: 1, 4, 7, 13, 25, 37, 41, 75, 83, 109 1. Insert the items in a particular order such that the resulting Binary Tree will be a balanced binary search tree (AVL Tree) and print the order of insertion to the screen (40 points). 2.. Print the pre-order traversal (20 points) 3. Print the in-order traversal (20 points) 4. Print the post-order traversal (20 points)