Write a C$++$ program that works with Linked Lists and performs the following operations:

traversal

Description: Will display each of the data stored in the BST depending on the input parameter:

$1.$ Preorder

$2.$ Inorder

$3.$ Postorder

$4.$ Level by level

Input: An integer $(1-4)$

Output: Nothing

Precondition: A valid BST

Postcondition: Nothing

height

Description: Will return the height of the BST

Input: Nothing

Output: An integer that will indicate the height of the BST

Precondition: A valid BST

Postcondition: Nothing

ancestors

Description: Will display the ancestors of a data

Input: The data whose ancestors you want to know

Output: Nothing

Precondition: A valid BST

Postcondition: Nothing

whatlevelamI

Description: Will return an integer that indicates the level at which a data is found, or $-1$ if it is not found in the BST

Input: A data to find its height

Output: Integer indicating the level of the data in the BST$,$ or $-1$ if it is not found

Precondition A valid BST

Postcondition Nothing

input:

n $//$ number of nodes to insert

n integer values

m $//$ number of nodes to remove

m integer values

q $//$ number of values $$to display their ancestors

q integer values

r $//$ number of values $$to display the level they are at

r integer values

output:

preorder traversal, values $$separated by exactly one space, the last value also has a space

inorder traversal, values $$separated by exactly one space, the last value also has a space

postorder traversal, values $$separated by exactly one space, the last value also has a space

level$-$by$-$level traversal, values $$separated by exactly one space, the last value also has a space

value of the total height of the tree without spaces at the end of the tree final

list of ancestors of the q values, separated by exactly one space, the last value also has a space

list of integers representing the level of each of the r values $$read$,$ one on each line, no trailing spaces

input example

$10$

$45$

$98$

$32$

$85$

$96$

$36$

$25$

$74$

$98$

$95$

$3$

$98$

$85$

$36$

$2$

$74$

$25$

$3$

$96$

$45$

$75$

output example

$453225957496$

$253245749596$

$253274969545$

$453295257496$

$3$

$4595$

$4532$

$2$

$0$

$-1$