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
	{
		//your code here
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                BST tree =  new BST();
                for(int i=0;i<n;i++){
                        tree.root = tree.insert(tree.root, sc.nextInt());
                }
              preOrderTraversal(tree.root);
        }}