## Tree Preorder 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). After forming the BST, print the Preorder traversal of the BST.

### Input Format

Line 1 contains integer n denoting number of nodes.

Line 2 contains n spaced integers denoting node values.

### Output Format

Print a single line of space separated integers denoting preorder traversal of tree.

### Example 1

Input

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

Output

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

Explanation

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

### Example 2

Input

```5
10 21 55 67 33
```

Output

```10 21 55 33 67
```

Explanation

```The BST is like :-
10
\
21
\
55
/  \
33  67
```

### Constraints

1<=n<=500

-1000<=value of node<=1000

## Solution of Tree Preorder 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;
}
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 preOrderTraversal(Node node){
if(node==null)
return;
System.out.print(node.val + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
public static void main (String[] args) throws java.lang.Exception
{