JAVA program to traverse inorder without recursion

Posted On // Leave a Comment

CODE:


import java.util.Scanner;
import java.util.Stack;

public class inorderStack{

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

    static node inputTree(){
        node temp=new node();
        System.out.print("Enter the value: ");
        temp.data=in.nextInt();
        System.out.print("Enter y if the node "+temp.data+" has left subtree: ");
        if(in.next().charAt(0)=='y')
            temp.left=inputTree();
        else
            temp.left=null;
        System.out.print("Enter y if the node "+temp.data+" has right subtree: ");
        if(in.next().charAt(0)=='y')
            temp.right=inputTree();
        else
            temp.right=null;
        return temp;
    }

    static void inorder(node tree){
        if(tree == null)
            return;
        Stack<node> s = new Stack<node>();
        while((s.isEmpty() == false)||(tree != null)){
            if(tree!=null){
                s.push(tree);
                tree = tree.left;
            }
            else{
                tree = s.pop();
                System.out.print(tree.data+"\t");
                tree = tree.right;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Enter the tree: ");
        node tree = new node();
        tree = inputTree();
        System.out.println("Inorder traversal ");
        inorder(tree);   
    }

}

0 comments :

Post a Comment