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
	{
		//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());
                }
                inOrderTraversal(tree.root);

        }}