write the java code that satisfy :

given a binary search tree $($BST$),$ show the order of keys when performing pre$-$order traversal, in$-$order wr

traversal, and post$-$order traversal?

Input Format

The first line contains the number of keys in the tree, $n.$

The second line contains the keys in the order at which they are inserted in the binary search tree.

Constraints

$1n{10}^5$

All keys are integers in the range $0$ to ${10}^5$

All inserted keys are guaranteed to be unique

Output Format

Three lines, as follows:

The first line contains the keys in pre$-$order traversal

The second line contains the keys in in$-$order traversal

The third line contains the keys in post$-$order traversal

Sample Input $0$