Saturday, 22 September 2018

TreeTraversal(InOrder,PreOrder,PostOrder) with recursion and without recursion

public class TreeTraversal {
    public static void main(String args[]) {
         Node rootNode = new Node("4");
         rootNode.left = new Node("2");
         rootNode.left.left = new Node("1");
         rootNode.left.right = new Node("3");
         rootNode.right = new Node("6");
         rootNode.right.right = new Node("7");
         rootNode.right.left = new Node("5");
        // System.out.println(rootNode);
         System.out.println("********pre order*********");
         preorderTraversal(rootNode);
         System.out.println("\n\n********in order*********");
         inorderTraversal(rootNode);
         System.out.println("\n\n********post order*********");
         postorderTraversal(rootNode);
         System.out.println("\n\n********* pre order without recursion******");
         preOrderWithoutRecursion(rootNode);
         System.out.println("\n\n********in order without recursion********");
         inOrderWithoutRecursion(rootNode);
         System.out.println("\n\n*******post without recursion****");
         postOrderWithoutRecursion(rootNode);
    }
   
    public static void preorderTraversal(Node rootNode) {
        if(null!=rootNode) {
            System.out.print(rootNode.value);
             preorderTraversal(rootNode.left);
             preorderTraversal(rootNode.right);
        }
    }
    public static void inorderTraversal(Node rootNode) {
        if(null!=rootNode) {
            inorderTraversal(rootNode.left);
             System.out.print(rootNode.value);
             inorderTraversal(rootNode.right);
        }
    }
    public static void postorderTraversal(Node rootNode) {
        if(null!=rootNode) {
            postorderTraversal(rootNode.left);
            postorderTraversal(rootNode.right);
             System.out.print(rootNode.value);
        }
    }
   
    public static void preOrderWithoutRecursion(Node root) {
        Stack<Node> stNodes = new Stack<>();
        Node current = root;
        while(!stNodes.isEmpty() || current!=null) {
            if(null!=current) {
                stNodes.push(current);
                System.out.print(current.value);
                current = current.left;
            }else {
                Node node = stNodes.pop();
               
                current = node.right;
            }
        }
    }
   
    public static void inOrderWithoutRecursion(Node root) {
        Stack<Node> stNodes = new Stack<>();
        Node current = root;
        while(!stNodes.isEmpty() || current!=null) {
            if(null!=current) {
                stNodes.push(current);
                current = current.left;
            }else {
                Node node = stNodes.pop();
                System.out.print(node.value);
                current = node.right;
            }
        }
    }
    public static void postOrderWithoutRecursion(Node root) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        Node current = root;
        stack1.push(root);
   
        while(!stack1.isEmpty() ) {
             Node node =  stack1.pop();
             stack2.push(node);
             if(null!=node.left) {
             stack1.push(node.left);
             }if(null!=node.right) {
                 stack1.push(node.right);
             }   
        }
       
        while(!stack2.isEmpty()) {
            System.out.print(stack2.pop().value);
        }
       
    }
   
}


class BinayTree{
    static class Node{
        String value;
        Node left;
        Node right;
       
        Node(String val){
            value = val;
            left = right = null;
        }
       
    }
   
}


output:
********pre order*********
4213657

********in order*********
1234567

********post order*********
1325764

********* pre order without recursion******
4213657

********in order without recursion********
1234567

*******post without recursion****
1325764

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...