Binary Tree Traversal using Recursive and Non-Recursive Methods [Java]

This program takes user input into a binary tree and the traverses the tress displaying the values using recursive and non recursive functions (Non recursive function for Inorder traversal):

Suppose the user inputs (-999 is taken as an end marker for input):

14 15 4 9 7 18 3 5 16 4 20 17 9 14 5 -999

The output of the program using both methods is (for Inorder traversal):

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20 

Java Code:

import java.util.Scanner;

class nodetype{
    public int info;
    public nodetype left;
    public nodetype right;
}

public class NonRecursiveInorderTreeTraversal {
    
    //General tree construction code
    static nodetype getnode(){
        return new nodetype();
    }
    
    static nodetype maketree(int x){
        nodetype p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        return p;
    }
    
    static void setleft(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.left != null)
            System.out.println("invalid insertion\n");
        else p.left = maketree(x);
    }
    
    static void setright(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.right != null)
            System.out.println("invalid insertion\n");
        else
         p.right = maketree(x);
    }
    
    /* Traversal in preorder, inorder and postorder */
    static void pretrav(nodetype tree){
        if(tree!=null){
            System.out.print(tree.info+" ");
            pretrav(tree.left);
            pretrav(tree.right);
        }
    }
    
    static void intrav(nodetype tree){
        if(tree!=null){
            intrav(tree.left);
            System.out.print(tree.info+" ");
            intrav(tree.right);
        }
    }
    
    static void posttrav(nodetype tree){
        if(tree!=null){
            posttrav(tree.left);
            posttrav(tree.right);
            System.out.print(tree.info+" ");
        }
    }
    /***   ***/

    
     private static int MAXSTACK = 100;
    

     //Code for the stack used
     static class stack{
         int top;
         nodetype[] item = new nodetype[MAXSTACK];
        
        {
            top = 0;
            item = new nodetype[MAXSTACK];
        }
        
         void push(nodetype it){
            if(top<MAXSTACK)
            item[top++] = it;
            else
                System.out.println("Stack Overflow!");
        }
         nodetype pop(){
            if(top!=0)
                return item[--top];
            else
                System.out.println("Nothing to pop!");
            return null;
        }
         boolean empty(){
            if(top==0){
                return true;
            }
            return false;
        }
    }
    

    //Non Recursive traversal method (inorder) using stack

    static void intrav2(nodetype tree){
        stack s = new stack();
        s.top = 0;
        
        nodetype p = tree;
        do{
            /* 
                travel down left branches as far as possible
                saving pointers to nodes passed
            */
            while(p!=null){
                s.push(p);
                p = p.left;
            } /*end while*/
            
            /*check if finished */
            if(!s.empty()){
                /* at this point the left subtree is empty */
                p = s.pop();
                System.out.print(p.info+" ");  /*visit the root*/
                p = p.right;                   /*traverse right subtree*/
            } /*end if*/
        }while(!s.empty() || p!= null);
    }/* end funtion */
    
    public static void main(String[] args){
        nodetype ptree;
        nodetype p = null, q;
        int number;
        
        System.out.println("Binary Tree Traversal\n\n");
        System.out.println("Enter numbers :");
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        
        ptree = maketree(number);
        
        while((number=scan.nextInt())!=-999){
            p = q = ptree;
            while(q!=null){
               p=q;
            if(number<p.info)
                q = p.left;
            else if(number>=p.info)
                q = p.right;
        }
    
         if (number<p.info)
            setleft(p, number);
         else if(number>=p.info)
            setright(p, number);
        }

        System.out.println("\nUsing recursive function intrav: ");        
        intrav(ptree);
        System.out.println("\nUsing non recursive function intrav2: ");
        intrav2(ptree);
    }
}