Postorder Traversal of binary tree in Java

1. Traverse the left subtree by recursively calling the post-order function.

2. Traverse the right subtree by recursively calling the post-order function.

3. Display the data part of the root (or current node).

class Node {

     int key;

     Node left, right;

     public Node(intitem) {

           key = item;

           left = right = null;

     }

}

class BinaryTree {

     /** Root of Binary Tree*/

     Node root;

     BinaryTree() {

           root = null;

     }

     /** PostOrder binary tree traversal. */

     void printPostorder(Node node) {

           if(node==null) {

                return;

           }

           printPreorder(node.left);

           printPreorder(node.right);

           System.out.print(node.key +" ");

          

     }

     /** Call PostOrder traversal. */

     void printPostorder() {

           printPreorder(root);

     }

}

public class PostorderTraversal {

     public static void main(String[] args) {

           BinaryTree bTree = newBinaryTree();

           bTree.root = new Node(1);

           bTree.root.left = new Node(2);

           bTree.root.right = new Node(3);

           bTree.root.left.left = new Node(4);

           bTree.root.left.right = new Node(5);

           bTree.root.left.left.left = new Node(6);

           bTree.root.left.left.right = new Node(7);

           System.out.println("PostOrder traversal of binary tree is ");

           bTree.printPostorder();

     }

}

Preorder Traversal of binary tree in Java

1. Display the data part of the root (or current node).

2. Traverse the left subtree by recursively calling the pre-order function.

3. Traverse the right subtree by recursively calling the pre-order function.

class Node {

     int key;

     Node left, right;

     public Node(intitem) {

           key = item;

           left = right = null;

     }

}

class BinaryTree {

     /** Root of Binary Tree*/

     Node root;

     BinaryTree() {

           root = null;

     }

     /** Inorder binary tree traversal. */

     void printPreorder(Node node) {

           if(node==null) {

                return;

           }

           System.out.print(node.key +" ");

          

           printPreorder(node.left);

           printPreorder(node.right);

     }

     /** Call InPrder traversal. */

     void printPreorder() {

           printPreorder(root);

     }

}

public class PreorderTraversal {

     public static void main(String[] args) {

           BinaryTree bTree = newBinaryTree();

           bTree.root = new Node(1);

           bTree.root.left = new Node(2);

           bTree.root.right = new Node(3);

           bTree.root.left.left = new Node(4);

           bTree.root.left.right = new Node(5);

           bTree.root.left.left.left = new Node(6);

           bTree.root.left.left.right = new Node(7);

           System.out.println("Preorder traversal of binary tree is ");

           bTree.printPreorder();

     }

}

Inorder Traversal of binary tree in Java

1. Traverse the left subtree by recursively calling the in-order function.

2. Display the data part of the root (or current node).

3. Traverse the right subtree by recursively calling the in-order function.

class Node {

      int key;

      Node left, right;

      public Node(int item) {

            key = item;

            left = right = null;

      }

}

class BinaryTree {

      /** Root of Binary Tree*/

      Node root;

      BinaryTree() {

            root = null;

      }

      /** Inorder binary tree traversal. */

      void printInorder(Node node) {

            if(node==null) {

                  return;

            }

            printInorder(node.left);

            System.out.println(node.key);

            printInorder(node.right);

      }

      /** Call InPrder traversal. */

      void printInorder() {

            printInorder(root);

      }

}

public class InorderTraversal {

      public static void main(String[] args) {

            BinaryTree bTree = new BinaryTree();

            bTree.root = new Node(1);

            bTree.root.left = new Node(2);

            bTree.root.right = new Node(3);

            bTree.root.left.left = new Node(4);

            bTree.root.left.right = new Node(5);

            bTree.root.left.left.left = new Node(6);

            bTree.root.left.left.right = new Node(7);

            System.out.println("\nInorder traversal of binary tree is ");

            bTree.printInorder();

      }

}

Program to detect loop in a linked list in Java

Use Hashing:

Traverse the list one by one and keep putting the node addresses in a Hash Map. If next of current node points to any of the previously stored nodes in HashMap then return true.

Mark Visited Nodes:

This solution requires modifications to basic linked list data structure.  Have a visited flag with each node.  Traverse the linked list and keep marking visited nodes.  If you see a visited node again then there is a loop.

Floyd’s Cycle-Finding Algorithm - fastest method:

Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Java code for Floyd’s Cycle-Finding Algorithm:

class LinkedList1 {

   Node start;

   /* Node - data & pointer for next node. */

   class Node {

      int data;

      Node next;

      Node(int d) {

         data = d; next = null;

      }

   }

   /* Inserts a new Node at start of list. */

   public void push(int value) {

      Node nNode = new Node(value);

      /** Make next of new Node as start */

      nNode.next = start;

      /** Move the start to point to new Node */

      start = nNode;

   }

   int detectLoop() {

      Node pSlow = start;

      Node pFast = start;

      while (pSlow != null && pFast != null && pFast.next != null) {

         pSlow = pSlow.next;

         pFast = pFast.next.next;

         if (pSlow == pFast) {

            System.out.println("Found loop in list");

            return 1;

         }

      }

      return 0;

   }

}

public class DetectLoopTest {

   public static void main(String args[])  {

      LinkedList1 list = new LinkedList1();

      list.push(10);

      list.push(40);

      list.push(12);

      list.push(13);

      /** Create loop to test. */

      list.start.next.next.next.next = list.start;

      list.detectLoop();

   }

}