Binary Tree traversal in Zigzag order and Level By Level in java

Here is the code for binary tree traversal
1. Normal Traversal
2. Zigzag Traversal
3. LevelByLevel Traversal.

The following Binary Tree is created  and traversal is done on that

     

import java.util.Stack;

/**
 *
 * @author Soumitra Chatterjee(onlinesoumitra@gmail.com)
 */
public class Tree {

    static Stack currentLevel = new Stack();
    static Stack nextLevel = new Stack();
    static Stack temp = new Stack();
    static boolean leftToRight = true;

    public static void main(String args[]) {
        Node rootnode = new Node(25);
        System.out.println(
                "Building tree with rootvalue " + rootnode.data);
        System.out.println("=================================");
        insert(rootnode, 11);
        insert(rootnode, 15);
        insert(rootnode, 9);
        insert(rootnode, 10);
        insert(rootnode, 6);
        insert(rootnode, 16);
        insert(rootnode, 23);
        insert(rootnode, 79);
        insert(rootnode, 66);
        insert(rootnode, 81);


        System.out.println("Traversing tree in order");
        System.out.println("=================================");
        printTree(rootnode);
        System.out.println("Traversing tree in Zigzag order");
        System.out.println("=================================");
        printTreeZigZag(rootnode);
        System.out.println("Traversing tree in Level by level");
        System.out.println("=================================");
        printLevelbyLevel(rootnode);
    }

    public static void insert(Node n, int value) {
        if (n == null) {
            return;
        }
        if (n.data > value) {
            if (n.left != null) {
                insert(n.left, value);
            } else {
                n.left = new Node(value);
                System.out.println("  Inserted " + value + " to left of node " + n.data);

            }
        } else if (n.data < value) {
            if (n.right != null) {
                insert(n.right, value);
            } else {
                n.right = new Node(value);
                System.out.println("  Inserted " + value + " to right of node " + n.data);

            }
            ///System.out.println("value = " + value);
        }
    }

    public static void printLevelbyLevel(Node n) {
        if (n == null) {
            return;
        }
        System.out.println("data = " + n.data);
        currentLevel.push(n);
        while (!currentLevel.isEmpty()) {
            Node x = (Node) currentLevel.pop();
            if (x != null) {
                // System.out.println("data  = " + x.data); 

                if (x.right != null) {
                    nextLevel.push(x.right);
                }
                if (x.left != null) {
                    nextLevel.push(x.left);
                }

                if (x.left != null) {
                    System.out.println("data = " + x.left.data);
                }
                if (x.right != null) {
                    System.out.println("data = " + x.right.data);
                }
            }




            if (currentLevel.isEmpty()) {

                temp = currentLevel;
                currentLevel = nextLevel;
                nextLevel = temp;

            }


        }
    }

    public static void printTreeZigZag(Node n) {
        if (n == null) {
            return;
        }
        currentLevel.push(n);
        while (!currentLevel.isEmpty()) {
            n = (Node) currentLevel.peek();
            Node x = (Node) currentLevel.pop();
            // System.out.println("data:" + x.data);
            if (n != null) {
                System.out.println("data  = " + x.data);

                if (leftToRight) {
                    if (x.left != null) {
                        nextLevel.push(x.left);
                    }
                    if (x.right != null) {
                        nextLevel.push(x.right);
                    }




                } else {
                    if (x.right != null) {
                        nextLevel.push(x.right);
                    }
                    if (x.left != null) {
                        nextLevel.push(x.left);
                    }
                    //righttoleft = true;
                }
            }
            if (currentLevel.isEmpty()) {
                leftToRight = !leftToRight;
                //swap stacks
                temp = currentLevel;
                currentLevel = nextLevel;
                nextLevel = temp;



                //  System.out.println("x = " + (Node)(nextLevel.pop());
            }
        }



    }

    public static void printTree(Node n) {
        if (n == null) {
            return;
        }
        System.out.println("root = " + n.data);
        if (n.left != null) {
            System.out.println("left child = " + n.left.data);
            printTree(n.left);
        }
        if (n.right != null) {
            System.out.println("right child = " + n.right.data);
            printTree(n.right);
        }
    }
}

class Node {

    int data;
    Node left;
    Node right;

    public Node(int val) {
        this.data = val;
    }
}

Linked list in Java

This blog in Linked list is meant for those who want a solution rather implementation of Linked list data structure in Java.Linked list implementation is very popular in C but when i searched for  its implementation in java code i found only few links where the logic is very complex.So i searched many books on java data structures and finally got some logic on Linked List from the book of Robert Sidgewick .
Now in Computer Science Linked list is a popular data structure which consist of group of nodes linked in a sequence using Nodes.

So the basic building blocks of Linked list requires two things

1. Nodes
2. Links

We can simply achieve this using this small piece of Java class class Node

class Node {
        int val;
        Node next;

        Node(int v) {
            System.out.println("Node created with val"+v);
            val = v;
        }
    }



Now if i create Object of node class like

Node n1 = new Node(1);//a Node with value 1

it will create object of node where n1.next is another Node.

Now say if we create another node n2 which is

Node n2=new Node(2);//a Node with value 2

and then point the n1.next to n2 i.e

n2=n1.next; 

will link the two nodes and the linked list will get created in the following way

Linked List with two nodes

A simple linked list implementation full code

/**

 *

 * @author Soumitra Chatterjee(onlinesoumitra@gmail.com)

 */

public class Linkedlist {

 /*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

 static class Node {

        int val;

        Node next;

        Node(int v) {

            val = v;

            // next = null;

        }

    }

    public static void main(String args[]) {

        Node n1 = new Node(1);

        Node n2=n1.next=new Node(2);

        System.out.println("n1 = " + n1.val);

        System.out.println("n2 = " + n1.next.val);//same as n2.val

    }

}

My next blog will be on circular linked list and Josephus Porblem solution using Linked list using JAVA.