JAVA program to build a tree from inorder and preorder traversals

Posted On // Leave a Comment

CODE:

import java.util.Scanner;

public class InPreToTree{

    static Scanner in = new Scanner(System.in);
    static int preIndex;

    static void inorder(node tree){
        if(tree==null)
            return;
        inorder(tree.left);
        System.out.print(tree.data+"\t");
        inorder(tree.right);
    }

    static void preorder(node tree){
        if(tree==null)
            return;
        System.out.print(tree.data+"\t");
        preorder(tree.left);
        preorder(tree.right);
    }

    static void postorder(node tree){
        if(tree==null)
            return;
        postorder(tree.left);
        postorder(tree.right);
        System.out.print(tree.data+"\t");
    }

    static node cnvrt(int[] inorder,int instart,int inend,int[] preorder){
            if((instart>inend))
                return null;
            node temp = new node();
            temp.data = preorder[preIndex++];
            if(instart==inend){
                temp.left=temp.right=null;
                return temp;
            }
            int i;
            for (i=0;(i<inorder.length)&&(inorder[i]!=temp.data);i++);
            temp.left = cnvrt(inorder,instart,i-1,preorder);
            temp.right = cnvrt(inorder,i+1,inend,preorder);
            return temp;
    }
   
    public static void main(String[] args) {
        int len;
        System.out.print("\nEnter length: ");
        len = in.nextInt();
        int[] iar = new int[len];
        int[] par = new int[len];
        int i;
        System.out.println("Enter inorder traversal");
        for(i=0;i<len;i++)
            iar[i] = in.nextInt();
        System.out.println("Enter preorder traversal");
        for(i=0;i<len;i++)
            par[i] = in.nextInt();
        node tree = new node();
        preIndex=0;
        tree = cnvrt(iar,0,len-1,par);
        System.out.println("Inorder traversal of the tree is:");
        inorder(tree);
        System.out.println("\nPreorder traversal of the tree is:");
        preorder(tree);
        System.out.println("\nPostorder traversal of the tree is");
        postorder(tree);
    }  
}

0 comments :

Post a Comment