## Tree Inorder Traversal in java

You are given the number of nodes present in the tree. You have to input the nodes and form a Binary Search Tree (BST).

BST should be formed in way like:

Let us consider an array named Val having the values of the nodes. Here, Val[0] will the root of BST. Then, you have to insert Val[1] in the BST, then insert Val[2] in the BST and so on….

After forming the BST, print the Inorder traversal of the BST.

#### Input Format

The first line contains an integer `n`, the number of nodes.

The next line contains the value of `n` nodes.

#### Output Format

Print the inorder traversal of the tree as a single line of space-separated values.

### Example 1

Input

```6
1 2 5 3 4 6
```

Output

```1 2 3 4 5 6
```

Explanation

```The BST is like :-
1
\
2
\
5
/  \
3    6
\
4

So, the inorder traversal of tree results in 1,2,3,4,5,6  as the required result.
```

#### Constraints

1 <= n <= 500

-1000 <= Val[node] <= 1000

## Solution of Tree Inorder Traversal in java:–

```import java.util.*;
import java.lang.*;
import java.io.*;

class Node{
int val;
Node left, right;
Node(int val){
this.val = val;
left = null;
right = null;
}
}
class BST{
Node root;
BST(){
root = null;
}
Node insert(Node node, int val){
if(node==null){
node = new Node(val);
return node;
}else if(val<node.val){
node.left = insert(node.left,val);
}else{
node.right = insert(node.right,val);
}
return node;
}
}

public class Main
{
public static void inOrderTraversal(Node node){
if(node==null)return;
inOrderTraversal(node.left);
System.out.print(node.val + " ");
inOrderTraversal(node.right);
}

public static void main (String[] args) throws java.lang.Exception
{