Postorder 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 PostOrder traversal of the BST.

Input Format

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

The next line inputs the value of n nodes.

Output Format

Print the trees postorder traversal as a single line of space-separated values.

Sample Input

6
1 2 5 3 6 4

Sample Output

4 3 6 5 2 1 

Explanation

The postorder traversal is shown.

The BST:

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

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

Constraints

1 <= Nodes in the tree <= 500

Solution of Postorder 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 postOrderTraversal(Node node){
                if(node==null)return;
                postOrderTraversal(node.left);
                postOrderTraversal(node.right);
                System.out.print(node.val + " ");
        }
	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());
                }
                postOrderTraversal(tree.root);

        }}